CT42496

Scribe's scrolls Tightest Stretch

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Scribe runs the signal tower at the marble forum of Argentium. Today the books show a list of scrolls, 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 <= 3795; 1 <= a[i] <= 1000000; 1 <= s <= 10^18.

Example 1:

Input: 3457 128372785 571051 435947 743102 438624 580997 485688 11063 145508 555852 990315 594888 546385 799387 614620 888928 239680 236513 311772 928531 292089 245964 302634 555281 581680 628243 944443 425931 130147 785119 970526 688924 829530 886357 636692 482907 806780 612329 383878 483032 552506 959026 765457 290031 72330 70784 19849 934058 298989 242569 670591 111005 498125 169376 159165 876778 581596 286217 533997 918195 943062 157970 865490 760801 942950 780489 798502 20092 504882 239363 821240 132772 430833 95519 653896 193951 785059 459376 767475 624709 628957 402036 470509 867059 990285 569383 714009 341382 860179 916239 482347 99653 930720 715445 127548 541851 393833 88679 197413 830475 389832 621998 920452 659230 825316 450738 657422 311524 834659 68186 89987 562606 119059 655753 9448…
Output: 232

Example 2:

Input: 2319 199214137 687152 294457 228637 938294 74322 177595 209308 370352 538320 87741 654191 319642 912090 851033 504216 166226 592972 738432 893685 646185 911229 200933 358668 660611 667593 654342 88444 228764 116134 662708 657768 88520 695291 926685 457058 233700 916531 301610 401329 148263 381639 203350 163085 340594 772518 961845 580361 508305 755871 221669 972225 387862 362223 905611 516942 641865 449566 389507 766425 116030 435487 482274 628893 718592 77149 411049 201142 937732 838488 623010 994374 407270 346960 751387 857413 928531 466112 685412 957977 308129 528638 404848 835376 290077 722212 455937 766716 693802 438407 843330 457689 108260 964141 888686 771462 36637 375338 547638 613952 308443 244520 248514 957428 249600 417935 322801 222834 566661 926980 729550 464937 518104 110374 …
Output: 377

Example 3:

Input: 2453 431979129 501589 331438 622678 688237 548491 247104 684969 444548 206008 111254 592551 275523 302812 488713 842472 435934 284077 823446 576946 715510 349728 723640 805718 18807 830367 485945 692178 807150 603048 772784 475455 618677 623109 889652 975725 710432 103468 557532 928867 952073 111590 407479 716822 641356 569927 635553 670298 605345 85739 754794 749075 100926 228236 396756 409936 72165 693965 781205 40870 498765 164138 341509 12021 794682 138394 919185 142981 336939 278471 215882 3753 612143 481732 624858 420508 427337 890356 69984 812373 392589 385717 691753 5689 68625 501516 612119 846392 472766 998873 929466 932249 999200 963057 689781 569451 554281 225090 255593 826764 362277 941151 646297 199477 74850 729897 463827 763122 858696 642434 864405 104904 687856 410130 376793…
Output: 852

Constraints:

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

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