CT42867

Tanya and the Tightest Stretch

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Tanya runs the tannery at the maple sugarbush of Saprun. Today the books show a list of stretches, and the numbers must be worked out before sundown. Task: All values are positive. Print the length of the shortest contiguous subarray whose sum is at least s, or 0 if none. Input format: First line: n and s. Second line: n positive integers. Output format: Print the minimum length, or 0 if impossible. Constraints: 1 <= n <= 1236; 1 <= a[i] <= 1000000000; 1 <= s <= 10^18.

Example 1:

Input: 787 135105753246 803765019 580800006 333510035 388278583 163165312 295444651 766104697 591603574 91830413 142910046 513592916 124684222 393527295 81130580 150267732 650956623 60468105 256904463 609426503 35311161 638819902 929904530 433787505 543013701 200998920 528757917 848097373 625571937 967434323 3567202 998847046 920187386 169473666 710801167 615463787 878217464 65968835 942287548 661922942 605913525 54694856 337756426 402696144 736814139 135456854 294843594 929670223 453695074 190319039 285674198 974612450 637251352 984662179 782008036 929614005 991202342 436333108 129091763 752276774 650279576 670477504 920270888 395754856 530016754 170539988 852424179 627826024 491904009 429607163 337847422 663295342 319373550 109569693 756333744 618390006 605476959 327722851 410464285 680937463 7…
Output: 256

Example 2:

Input: 38 3886432211 453126177 386709057 498787103 259311287 744748993 265826800 463970717 113006585 957956798 733243527 468794363 221164426 189502774 73406963 542113382 39980613 751040974 281447241 603133610 913214157 20672688 167589351 281260272 236146515 471510377 537582741 813891282 645902614 406851552 939360296 767824349 700389065 305435122 343066680 641915062 184447962 250443592 481373725
Output: 6

Example 3:

Input: 1004 305471374736 602972207 527621840 259802939 543999154 191730840 92319352 368235192 743566486 673350673 800413616 76345398 510751563 721534408 563924336 349954001 261617269 820461771 587600224 491810350 710016995 648928113 783647305 87420112 834523603 558084338 928077682 110894205 665194368 913216165 894774761 972294790 493760836 933157645 994097780 245199774 529041057 454957395 544068546 580535173 263087780 788949412 420435179 428397458 916501102 122047794 970430606 492112087 324680488 190617358 896458732 382494336 616450932 684592945 718780110 828880301 499465290 957053 442520179 696582029 287289143 976833917 517055159 639347584 389270904 548508844 772791477 367211804 345467008 998971659 649347242 211266273 218362333 706487315 480430512 995033049 51084928 35049028 782045694 25536684 6…
Output: 604

Constraints:

1 <= n <= 1236; 1 <= a[i] <= 1000000000; 1 <= s <= 10^18.

Loading...
Test Cases:No test cases
No test cases available.