ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#5952

열차 다리 1s 1024MB

問題

열차가 다리를 건너려고 합니다.

열차의 각 칸의 길이는 10m이지만 무게는 다를 수 있습니다.

다리의 길이는 40m입니다(따라서 한 번에 네 칸을 수용할 수 있습니다).

다리 위에 놓인 차량의 총 중량이 특정 중량보다 크면 다리가 갈라집니다.

열차의 각 칸에는 1부터 시작하여 N까지 번호가 매겨져 있으며, 순서대로 다리를 건너갑니다 (예: 1 바로 다음에 2, 바로 다음 3).

열차의 각 칸 1...T가 순서대로 다리를 건너게 된다면 다리를 안전하게 건널 수 있는 가장 큰 열차 칸 수 T는 무엇입니까?


入力

첫 줄은 다리가 한 번에 지탱할 수 있는 최대 무게 W(1 ≤ W ≤ 100\ 000)가 주어진다.

두 번째 줄은 다리를 건너 이동하려는 열차의 칸 수 N(1 ≤ N ≤ 100\ 000)이 주어진다.

다음 N줄에는 각각 i번째 철도 차량의 무게를 나타내는 양의 정수 w_i (1 ≤ i ≤ N, 1 ≤ w_i ≤ 100000 ) 가 주어진다.


出力

순서대로 열차가 다리를 지나간다면 다리를 건널 수 있는 가장 큰 열차 칸 수 T를 출력한다.


例題 

100
6
50
30
10
10
40
50
5

처음 4 칸의 총 무게는 50 + 30 + 10 + 10 = 100이며 이는 다리가 지탱할 수 있는 것보다 크지 않습니다.

첫 번째 칸이 건너고 다음 열차 칸이 들어올 때 총 무게는 30 + 10 + 10 + 40 = 90이 되며 이는 다리가 지탱할 수 있는 것보다 크지 않습니다.

그러나 그 다음에는 10 + 10 + 40 + 50 = 110이 되어 다리가 지탱할 수 있는 것보다 크기 때문에 첫 5 칸의 열차만이 다리를 안전하게 건너갈 수 있습니다.


出典

CCC 2013 Senior Division 2번
ログインしないとコードを書けません。