시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB97916511725.602%

문제

길이가 N인 정수 수열과 정수 X가 주어진다. 이때, 합이 X보다 크거나 같은 연속 부분 수열 중에서 길이가 가장 짧은 것을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N (1 ≤ N ≤ 500,000)과 X (-109 ≤ X ≤ 109)가 주어진다. 둘째 줄에는 수열에 들어있는 정수 N개가 주어진다. 이 정수는 -109보다 크거나 같고, 109보다 작거나 같다.

출력

각 테스트 케이스마다 합이 X보다 크거나 같은 연속 부분 수열 중 가장 짧은 길이를 출력한다. 만약, 그러한 배열이 없는 경우에는 -1을 출력한다.

예제 입력 1

3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1

예제 출력 1

3
-1
3
W3sicHJvYmxlbV9pZCI6Ijk2MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjODE1XHVjMjE4IFx1YzIxOFx1YzVmNFx1YWNmYyBcdWM4MTVcdWMyMTggWFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVkNTY5XHVjNzc0IFhcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1ZjBcdWMxOGQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOICgxICZsZTsgTiAmbGU7IDUwMCwwMDApXHVhY2ZjIFggKC0xMDxzdXA+OTxcL3N1cD4gJmxlOyBYICZsZTsgMTA8c3VwPjk8XC9zdXA+KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMTggTlx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgLTEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDxzdXA+OTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NjlcdWM3NzQgWFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzVmMFx1YzE4ZCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhZGY4XHViN2VjXHVkNTVjIFx1YmMzMFx1YzVmNFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NjIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWluaW1hbCBTdWJhcnJheSBMZW5ndGgiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYW4gaW50ZWdlciBzZXF1ZW5jZSBvZiBsZW5ndGggTiBhbmQgYW5vdGhlciB2YWx1ZSBYLiBZb3UgaGF2ZSB0byBmaW5kIGEgY29udGlndW91cyBzdWJzZXF1ZW5jZSBvZiB0aGUgZ2l2ZW4gc2VxdWVuY2Ugc3VjaCB0aGF0IHRoZSBzdW0gaXMgZ3JlYXRlciBvciBlcXVhbCB0byBYLiBBbmQgeW91IGhhdmUgdG8gZmluZCB0aGF0IHNlZ21lbnQgd2l0aCBtaW5pbWFsIGxlbmd0aC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgVCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIDIgaW50ZWdlcnMgTigxJmxlO04mbGU7NTAwMDAwKSBhbmQgWCgtMTA8c3VwPjk8XC9zdXA+JmxlO1gmbGU7MTA8c3VwPjk8XC9zdXA+KS4gTmV4dCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgZGVub3RpbmcgdGhlIGVsZW1lbnRzIG9mIHRoZSBzZXF1ZW5jZS4gVGhlc2UgaW50ZWdlcnMgd2lsbCBiZSBiZXR3ZWVuIC0xMDxzdXA+OTxcL3N1cD4gdG8gMTA8c3VwPjk8XC9zdXA+IGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2Ugb3V0cHV0IHRoZSBtaW5pbXVtIGxlbmd0aCBvZiB0aGUgc3ViIGFycmF5IHdob3NlIHN1bSBpcyBncmVhdGVyIG9yIGVxdWFsIHRvIFguIElmIHRoZXJlIGlzIG5vIHN1Y2ggYXJyYXksIG91dHB1dCAtMS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Thailand > 2013 ACM-ICPC Asia Phuket Regional Programming Contest J번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: jh05013