시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 161 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을 출력한다.

예제 입력 1

5 10000
1
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
W3sicHJvYmxlbV9pZCI6IjI4NTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD4yKktcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWNjOThcdWM3NGMgS1x1YWMxY1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVkNTY5XHVhY2ZjIFx1YjljOFx1YzljMFx1YjljOSBLXHVhYzFjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWQ1NjlcdWM3NzQgU1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNWY0XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMDZjXHVhZTMwXHVhYzAwIE5cdWM3NzggXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODQgXHVjNWYwXHVjMThkIFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlO04gJmxlOyAxMDAsMDAwLCAxICZsZTsgUyAmbGU7Jm5ic3A7MiZ0aW1lczsxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0IEFcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YjI5NCBcdWM1OTFcdWMyMThcdWM3NzRcdWJhNzAsIFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVkNTY5XHVjNzQwIDImdGltZXM7MTA8c3VwPjk8XC9zdXA+XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzZkMFx1YzE4Y1x1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWIyOTQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRWT05JWiIsImRlc2NyaXB0aW9uIjoiPHA+V2Ugc2F5IHRoYXQgYSBzZXF1ZW5jZSBvZiAyKksgZWxlbWVudHMgaXMgaW50ZXJlc3RpbmcgaWYgbmVpdGhlciB0aGUgc3VtIG9mIHRoZSBmaXJzdCBLIGVsZW1lbnRzLCBub3IgdGhlIHN1bSBvZiB0aGUgbGFzdCBLIGVsZW1lbnRzLCBpcyBncmVhdGVyIHRoYW4gUy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzZXF1ZW5jZSBBIG9mIGxlbmd0aCBOIGlzIGdpdmVuLiBGb3IgZXZlcnkgZWxlbWVudCwgb3V0cHV0IHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgaW50ZXJlc3Rpbmcgc3Vic2VxdWVuY2Ugc3RhcnRpbmcgd2l0aCB0aGF0IGVsZW1lbnQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBpbnRlZ2VycyBOIGFuZCBTICgyICZsZTsgTiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBTICZsZTsgMioxMDxzdXA+OTxcL3N1cD4pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiB0aGUgc2VxdWVuY2UgQSwgb25lIGludGVnZXIgcGVyIGxpbmUuIFRoZSBpbnRlZ2VycyBhcmUgcG9zaXRpdmUgYW5kIHRoZWlyIHN1bSBkb2VzIG5vdCBleGNlZWQgMioxMDxzdXA+OTxcL3N1cD4uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG11c3QgY29uc2lzdCBvZiBOIGxpbmVzLiBpLXRoIGxpbmUgbXVzdCBjb250YWluIG9uZSBpbnRlZ2VyLCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IGludGVyZXN0aW5nIHN1YnNlcXVlbmNlIHN0YXJ0aW5nIHdpdGggdGhlIGktdGggZWxlbWVudC4gSWYgYW4gaW50ZXJlc3Rpbmcgc3Vic2VxdWVuY2UgYXQgdGhhdCBwb3NpdGlvbiBkb2VzbiZyc3F1bzt0IGV4aXN0LCBvdXRwdXQgMCAoemVybykuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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