시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 160 38 34 27.200%

문제

2*K개로 이루어진 수열이 있을 때, 처음 K개의 원소의 합과 마지막 K개의 원소의 합이 S를 넘지 않을 때, 이 수열을 흥미로운 수열이라고 한다.

크기가 N인 수열이 주어졌을 때, 각각의 수열의 원소에서 시작하는 부분 연속 수열 중 가장 긴 흥미로운 수열의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 S가 주어진다. (2 ≤N ≤ 100,000, 1 ≤ S ≤ 2×109)

둘째 줄부터 N개의 줄에 수열 A의 원소가 한 줄에 하나씩 주어진다. 이 수는 양수이며, 수열 A의 모든 원소의 합은 2×109를 넘지 않는다.

출력

출력은 총 N개의 줄로 이루어져 있다. i번째 줄에는 i번째 원소에서 시작하는 가장 긴 흥미로운 수열의 길이를 출력한다. 만약 흥미로운 수열이 없을 때는 0을 출력한다.

예제 입력

5 10000
1
1
1
1
1

예제 출력

4
4
2
2
0

예제 입력 2

5 9
1
1
10
1
9

예제 출력 2

2
0
0
2
0

예제 입력 3

8 3
1
1
1
1
1
1
1
1

예제 출력 3

6
6
6
4
4
2
2
0

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #5 5번