CT41987

Librarian's segments Tightest Stretch

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Librarian runs the granary at the glass towers of Prismhaven. Today the books show a list of segments, 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 <= 3233; 1 <= a[i] <= 1000000; 1 <= s <= 10^18.

Example 1:

Input: 871 421789261 44383 104447 466273 252423 803031 257961 790916 27644 455779 426605 167805 753354 747619 343349 557577 846540 547386 148409 46991 806004 376408 252152 372699 967987 54304 141266 793548 242785 436724 409787 148705 371168 645362 988927 674336 243190 24562 963680 167934 723872 943217 83404 851412 394766 353788 700537 435662 784012 938964 494247 37878 97652 939800 578959 549540 413106 858207 924036 620800 855416 86830 800004 959499 926728 838586 179998 18839 988664 18335 316098 495316 258098 814282 2306 962538 109918 869445 754356 802178 338655 337732 924333 974722 803471 269937 191769 802948 847686 782441 167574 173825 534794 90999 924369 352659 227641 861692 917125 130695 885657 818228 120269 81725 626819 489070 597614 706466 162919 637510 494233 938811 576184 335158 934587 746…
Output: 819

Example 2:

Input: 16 446768 335511 718463 243295 58504 96538 34563 261093 451349 118582 994689 51684 154736 538299 492839 537104 493930
Output: 1

Example 3:

Input: 1511 327546356 712327 11514 647798 828522 666042 471963 353766 255543 907587 65025 208945 620870 282690 320295 205630 565675 160733 660029 315103 932808 293869 777165 242530 971695 629400 696215 614312 685002 403246 803933 531871 25110 174348 592968 435039 894176 349894 874073 56972 822023 721503 307660 120421 858008 293041 324801 203706 118999 443314 107634 820774 770449 617815 359244 269558 223981 230670 868641 306245 428897 740744 114599 549143 529508 930353 887633 186387 757384 869699 940452 703651 259574 173297 220865 939405 47777 739864 977563 918159 679006 419096 206455 503975 100124 422164 205719 763021 601861 724055 476465 399124 979083 363048 250249 773316 398156 80073 257268 891543 4669 25998 231002 171310 194379 469995 732578 581895 459879 536248 79334 472658 237986 438771 9215…
Output: 613

Constraints:

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

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