CT50696

Cartwright's Rustic segments

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the river town of Willowford with crates of segments, and Cartwright the log keeper must account for every last one. 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 <= 3040; 1 <= a[i] <= 1000000000; 1 <= s <= 10^18.

Example 1:

Input: 1714 688227444125 348723453 9888916 576888040 662032150 729570299 951579597 293284101 374915650 669665378 638875736 509768983 501656088 251221751 68044994 810605665 19027161 986356088 273637633 673190941 350554565 210930549 303466638 368602754 690078895 821935731 968967298 735883288 900765258 760274545 902233269 741539984 766466685 3122686 101733023 252871410 381180959 919402059 659824897 550900443 840523261 14771432 815544718 263694118 730615276 260883356 26404425 173610692 496711719 430525221 668395858 784950963 345769980 706708709 792275214 609599618 240760693 389077647 244151648 323174182 20100464 664996647 680685677 243694038 631221203 129387083 681464012 130403782 212716909 952922363 806084200 553831125 312907868 187234314 595588883 982720609 410253157 226009422 104895502 529404815 8…
Output: 1353

Example 2:

Input: 1432 673555701022 674892587 780460511 705571958 570430122 707116189 942692096 867789017 633909535 352087978 32409660 410531273 591338440 88105717 673247212 252915211 89322936 399065108 208675180 811391097 518287749 649723798 679552522 909000667 262576748 362021835 929804449 489368506 915610838 94628329 494073589 5373107 559275799 522382464 433557204 669966056 47269617 690749373 70518681 432969461 182153186 33898606 772130066 443445385 115441973 526952566 301237002 965896137 482562485 825718345 543457735 738946613 741960288 286570351 35239486 366702842 185838393 448588617 243365003 15162762 228397230 842205978 380497525 701278309 136264740 98043235 725695121 244088145 540095936 715558166 938854805 253677132 431721095 400093382 519297603 903670226 495750349 257706855 994212107 430934583 6361…
Output: 1381

Example 3:

Input: 546 3643151374 543511130 311456689 141933016 48847833 827566410 252271166 61229045 783041614 668679620 17702332 317707384 568676073 12176884 669192867 438105010 366480822 989718602 731168057 696909608 471435908 515822666 454415036 769412639 192709483 462812067 450818173 41600247 915360662 559487089 457794217 234087603 132099783 972340899 473090502 438863245 665597655 194923478 803913000 157972336 406691921 578269039 493369156 800608409 528106860 56638991 847371178 607590980 997934089 518390026 329649401 671874117 982287417 65697863 475090935 391514082 873695142 17659597 55024341 774059702 785272650 387702749 34054338 343291643 319762534 465459239 625608405 87012550 606569948 780603573 134072177 245457484 780352991 492726899 276224065 923999060 905887021 774183644 103760770 932728553 416813…
Output: 4

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Cartwright's Rustic segments - MEDIUM Coding Problem | CodeTikki