시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5775 1360 1072 28.337%

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE4MDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWJkODRcdWQ1NjkiLCJkZXNjcmlwdGlvbiI6IjxwPjEwLDAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzQgTlx1YzlkY1x1YjlhYyZuYnNwO1x1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNWYwXHVjMThkXHViNDFjIFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWJkODBcdWJkODRcdWQ1NjkgXHVjOTExXHVjNWQwIFx1YWRmOCBcdWQ1NjlcdWM3NzQgUyBcdWM3NzRcdWMwYzFcdWM3NzQgXHViNDE4XHViMjk0IFx1YWM4MyBcdWM5MTEsIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzgzXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiAoMTAgJmxlOyBOICZsdDsgMTAwLDAwMClcdWFjZmMmbmJzcDtTICgwICZsdDsgUyAmbGU7IDEwMCwwMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWMwMSBcdWM2ZDBcdWMxOGNcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIDEwLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkNmNcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM3N2MgXHVhZGY4XHViN2VjXHVkNTVjIFx1ZDU2OVx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTgwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1YnNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5BIHNlcXVlbmNlIG9mIE4gcG9zaXRpdmUgaW50ZWdlcnMgKDEwICZsZTsgTiAmbHQ7IDEwMCAwMDApLCBlYWNoIG9mIHRoZW0gbGVzcyB0aGFuIG9yIGVxdWFsIDEwMDAwLCBhbmQgYSBwb3NpdGl2ZSBpbnRlZ2VyIFMgKFMgJmxlOyAxMDAgMDAwIDAwMCkgYXJlIGdpdmVuLiBXcml0ZSBhIHByb2dyYW0gdG8gZmluZCB0aGUgbWluaW1hbCBsZW5ndGggb2YgdGhlIHN1YnNlcXVlbmNlIG9mIGNvbnNlY3V0aXZlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZSwgdGhlIHN1bSBvZiB3aGljaCBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gUy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk1hbnkgdGVzdCBjYXNlcyB3aWxsIGJlIGdpdmVuLiBGb3IgZWFjaCB0ZXN0IGNhc2UgdGhlIHByb2dyYW0gaGFzIHRvIHJlYWQgdGhlIG51bWJlcnMgTiBhbmQgUywgc2VwYXJhdGVkIGJ5IGFuIGludGVydmFsLCBmcm9tIHRoZSBmaXJzdCBsaW5lLiBUaGUgbnVtYmVycyBvZiB0aGUgc2VxdWVuY2UgYXJlIGdpdmVuIGluIHRoZSBzZWNvbmQgbGluZSBvZiB0aGUgdGVzdCBjYXNlLCBzZXBhcmF0ZWQgYnkgaW50ZXJ2YWxzLiBUaGUgaW5wdXQgd2lsbCBmaW5pc2ggd2l0aCB0aGUgZW5kIG9mIGZpbGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGhlIGNhc2UgdGhlIHByb2dyYW0gaGFzIHRvIHByaW50IHRoZSByZXN1bHQgb24gc2VwYXJhdGUgbGluZSBvZiB0aGUgb3V0cHV0IGZpbGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2006 B번

  • 문제를 번역한 사람: author5
  • 시간 제한을 수정한 사람: cheetose
  • 잘못된 조건을 찾은 사람: isku
  • 데이터를 추가한 사람: wookje YunGoon
  • 문제의 오타를 찾은 사람: ZZangZZang