R02187
예산 안의 최장 여행
실버 IV레이팅
의견: 0
설명
\(N\)개의 도시가 일렬로 놓여 있고, \(i\)번째 도시에서 하루 머무는 비용이 \(a_i\)이다.
여행자는 연속한 도시들만 순서대로 방문할 수 있으며, 방문한 도시들의 비용 합이 예산 \(S\)를 넘지 않아야 한다. 이 조건을 지키면서 방문할 수 있는 연속 도시의 최대 개수를 구하여라. (한 도시도 방문하지 못하면 \(0\)을 출력한다.)
제약
\(1 \le N \le 100\,000\), \(1 \le a_i \le 10^9\), \(1 \le S \le 10^{18}\)
입력 형식
첫째 줄에 도시의 수 \(N\)과 예산 \(S\)가 주어진다.
둘째 줄에 \(N\)개의 비용 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
예산 안에서 연속으로 방문할 수 있는 도시 최대 개수를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 30점 | \(1 \le N \le 400\) |
Subtask 2 | 70점 | 추가 제약이 없다. |
예제 1
입력
7 8
3 1 2 1 4 2 1
출력
4
설명
\([3,1,2,1]\)의 합은 \(7\le 8\)로 길이 \(4\)이며 더 긴 구간은 없다.
예제 2
입력
5 3
5 1 1 1 5
출력
3
설명
합이 \(3\) 이하인 가장 긴 구간은 \([1,1,1]\)로 길이 \(3\)이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
예산 안의 최장 여행
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
예산 안의 최장 여행
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기