A00012
알파카컵 2회: B - 알파카의 간식 구간
골드 V레이팅
의견: 0
설명
알파카는 일렬로 놓인 \(N\)개의 간식 상자를 발견했다.
\(i\)번째 상자에는 \(A_i\)개의 간식이 들어 있다. 알파카는 연속한 몇 개의 상자를 골라 간식을 먹으려고 한다.
하지만 한 번에 너무 많이 먹으면 졸리기 때문에, 고른 연속 구간에 들어 있는 간식의 총합이 \(K\)개 이하이어야 한다.
조건을 만족하는 연속 구간의 개수를 구하시오.
제약
- \(1 \le N \le 200{,}000\)
- \(1 \le K \le 10^{18}\)
- \(1 \le A_i \le 10^9\)
- 모든 입력값은 정수이다.
입력 형식
첫째 줄에 상자의 개수 \(N\)과 최대 간식 개수 \(K\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.
출력 형식
간식의 총합이 \(K\) 이하인 연속 구간의 개수를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 10점 | \(1 \le N \le 100\) |
Subtask 2 | 20점 | \(1 \le N \le 2000\) |
Subtask 3 | 30점 | \(1 \le N \le 50000\) |
Subtask 4 | 40점 | 추가 제한 없음. |
예제 1
입력
5 5
1 2 3 4 5출력
7예제 2
입력
4 100
10 20 30 40출력
10문제 정보
태그
평가 및 의견
알파카컵 2회: B - 알파카의 간식 구간
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
알파카컵 2회: B - 알파카의 간식 구간
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기