CT53070

The Crimson stretches of Sona

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the frontier camp of Duskwood opens only for a perfect tally of stretches. Sona 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 <= 3393; 1 <= a[i] <= 1000; 1 <= s <= 10^18.

Example 1:

Input: 3073 73798 960 558 118 662 801 591 925 823 754 111 176 30 943 662 74 247 472 686 569 137 472 934 143 647 302 4 537 170 202 256 325 866 424 942 914 691 104 547 422 577 154 355 502 854 699 401 384 94 107 316 46 729 222 40 867 796 429 515 165 265 988 368 432 791 639 723 924 112 274 514 183 812 424 312 567 277 748 221 646 69 133 387 852 333 923 794 816 733 640 135 9 96 844 708 80 634 698 161 294 876 501 26 187 458 103 176 680 809 411 593 345 393 878 194 824 980 819 612 107 940 963 207 181 58 214 953 160 772 48 100 451 44 6 196 833 969 767 860 993 290 807 406 475 189 554 647 431 316 965 480 402 622 533 662 883 481 747 900 195 112 115 50 144 13 600 826 385 689 816 508 613 676 366 741 385 518 545 319 804 883 649 235 842 108 360 526 300 246 821 122 118 554 385 498 383 497 640 977 615 719 575 444 5…
Output: 131

Example 2:

Input: 2071 461712 841 350 106 245 689 686 912 868 590 666 674 542 472 977 454 775 397 767 604 964 404 664 537 699 547 956 210 435 363 123 954 42 443 715 215 625 866 914 141 740 552 641 700 571 711 636 64 360 708 64 289 730 119 518 94 270 410 494 745 212 356 895 710 811 701 559 371 849 274 72 163 393 76 49 843 47 989 61 540 657 441 789 527 412 929 572 372 771 967 55 187 187 344 572 581 643 218 654 189 541 844 810 477 620 480 386 144 528 663 465 237 587 574 270 448 642 452 818 967 928 425 584 549 948 384 31 144 900 566 221 106 90 582 501 266 721 792 526 297 766 308 933 872 791 44 727 731 734 498 929 420 884 169 307 953 328 894 269 387 327 420 424 59 642 458 948 9 933 118 498 965 990 594 883 508 873 193 774 894 357 407 535 582 606 60 665 703 291 518 754 716 453 15 554 453 214 755 410 570 425 369 99…
Output: 926

Example 3:

Input: 3381 1139299 144 604 532 180 528 533 335 147 46 220 188 526 767 995 789 337 587 829 480 719 873 608 421 73 105 941 708 632 737 644 65 685 386 534 909 637 704 707 899 525 228 869 226 96 856 478 139 159 201 306 151 469 445 239 721 142 796 394 123 522 435 188 382 393 473 133 435 436 347 682 153 989 16 972 289 534 430 727 961 695 974 426 192 356 628 984 369 292 41 596 47 694 132 418 675 909 193 870 71 804 972 887 210 912 763 422 119 577 157 413 267 404 9 903 853 909 294 852 339 252 746 420 572 813 556 65 752 712 754 43 346 11 112 837 590 886 453 739 19 68 224 462 352 268 941 396 993 586 338 424 406 159 561 500 496 57 535 315 273 186 545 744 282 364 337 182 986 834 182 627 355 400 131 456 955 266 927 406 921 500 301 620 957 775 363 245 365 261 277 63 676 249 319 132 987 150 169 598 902 688 3 90…
Output: 2277

Constraints:

1 <= n <= 3393; 1 <= a[i] <= 1000; 1 <= s <= 10^18.

Loading...
Test Cases:No test cases
No test cases available.
The Crimson stretches of Sona - MEDIUM Coding Problem | CodeTikki