CT42086

The stretches Tightest Stretch Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the rook towers of Chessfield opens only for a perfect tally of stretches. Rowena means to find out. 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 <= 1558; 1 <= a[i] <= 1000000; 1 <= s <= 10^18.

Example 1:

Input: 908 346916164 416644 416851 511683 548621 273 837846 540770 88327 813844 445788 84319 713071 444077 591873 96159 203284 323554 92764 949165 308863 804446 446989 709478 201296 5228 701004 650945 768728 361118 518784 205290 985937 803319 298331 853546 773950 492751 118730 978234 667315 726194 229093 809589 797675 682700 223945 604764 301615 907685 464938 130438 300573 974545 759558 691209 623185 934705 951727 718495 959512 147509 214667 772056 179811 612772 619868 511486 808586 735829 38436 649593 201532 957625 11160 898444 252197 353601 922561 384571 619662 976194 191060 88908 851808 149071 688245 188212 588187 79017 375853 887221 33738 350241 255592 103073 724016 920907 614759 161897 994264 620723 475302 261847 820005 16953 895330 680740 540107 236023 980362 64911 656520 280439 927027 8591…
Output: 687

Example 2:

Input: 1484 337837476 744439 825391 267837 500729 468467 319044 919564 7503 297428 695294 257524 214682 925022 139529 151164 331237 675220 728927 854767 808444 343761 3110 604360 355904 982830 730321 253991 680948 923783 407039 915040 160305 409900 752888 749107 708258 517845 734063 519167 558611 952475 175887 43260 20345 964543 428837 987648 642892 312119 162185 131144 254814 465803 527827 843417 913617 982053 712731 748255 531450 437676 632693 562231 821165 457270 971061 60649 68797 65018 480698 318634 155229 429385 26992 435126 192865 795507 570771 17762 383981 822514 12612 263490 95554 327571 963395 993714 810866 709276 799165 133416 614933 786489 982538 195098 120003 264763 446881 475156 601813 571629 381015 652379 639208 294080 593499 162301 54549 689321 48144 370763 257378 373397 876838 97…
Output: 671

Example 3:

Input: 1105 269235149 777822 34034 598668 551599 457018 547476 903906 244539 609831 233113 258749 704438 721677 215172 703387 270906 635014 635962 904881 996499 859664 727744 211351 842778 69323 86152 385241 652787 516574 555867 727549 893144 944154 520206 125737 929887 346642 849447 48197 780979 573459 570927 724620 767501 112954 177061 134669 149432 102431 613515 845505 523563 281298 812529 495500 20054 117154 321831 691047 705661 659999 318986 723132 605074 91813 853072 516817 589382 880924 740310 360682 316517 192436 524231 494027 592815 500434 925746 227564 425510 682994 546656 705326 34514 712061 102407 954213 982680 492125 236669 956024 437319 709414 406370 944755 824211 595094 900372 28306 108423 329375 524165 993821 667332 486574 489343 910690 621564 942639 810879 844044 976588 404924 30…
Output: 513

Constraints:

1 <= n <= 1558; 1 <= a[i] <= 1000000; 1 <= s <= 10^18.

Loading...
Test Cases:No test cases
No test cases available.
The stretches Tightest Stretch Puzzle - MEDIUM Coding Problem | CodeTikki