CT47056

The ribbons at Verdigris

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the copper works of Verdigris as Aria unrolls the day's manifest of ribbons. The tally will decide the next shipment. 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 <= 1504; 1 <= a[i] <= 1000000; 1 <= s <= 10^18.

Example 1:

Input: 258 65867161 365561 203098 596972 415273 862788 310500 354867 503239 669611 420314 151931 849150 965208 128732 285798 501981 835244 347952 999636 354678 333735 879943 352101 773894 691215 458446 870101 896555 833419 436776 982913 174366 748949 267168 196799 731713 232640 410497 557246 705542 227513 256057 225347 682765 299440 37847 322706 253662 39753 598066 33764 407109 583256 742700 772304 5363 371358 242954 1748 747732 351860 82478 611493 706825 131494 335385 564557 621228 228420 536456 822703 879081 261260 814740 940659 829357 165120 964799 19290 311577 806557 247676 459311 543885 521043 610054 307270 590603 552674 500027 140285 162408 464835 613773 289948 718687 315382 308501 633199 558834 937577 243406 321342 956019 342188 141714 298054 655261 846253 409655 374304 149963 6355 876982 …
Output: 133

Example 2:

Input: 1308 593587630 395401 261953 631699 595216 816888 441071 851773 259402 608586 418544 854079 730215 985424 849883 527880 778713 882346 677402 411972 161239 149081 616320 839587 811883 151158 367693 50479 318029 81153 716133 17338 504965 132637 546280 52397 991062 393194 397480 681478 206581 22892 112037 771242 940384 64523 88039 427879 295559 308173 310381 997892 411845 821895 378217 321666 659513 644536 411581 285787 774821 118629 281243 483184 934583 435094 542413 227520 38522 827034 823592 148260 727032 329551 692316 372397 224340 879219 957070 468438 612017 539324 33529 810207 458617 162647 946995 44277 884941 338529 940661 607161 665876 67256 544814 602379 374417 571287 624971 560163 760922 479186 129878 72402 489547 181253 954431 738087 803973 90860 334530 994605 361602 745554 557771 …
Output: 1186

Example 3:

Input: 164 26511431 793444 167066 800893 268862 628399 609986 944652 90966 739673 958676 673710 397113 240669 697417 189458 800974 239450 625659 891097 299052 699790 602708 45333 824606 386874 350688 373309 704383 142861 657284 729347 268149 710140 546703 414684 531337 433963 968167 379811 440219 558446 682964 595979 433332 410210 357463 919224 943859 957711 870438 992379 158229 906622 353261 876774 798566 399165 809982 235328 169765 929026 298946 742410 761995 252527 299605 599058 537830 473139 675244 958152 49466 602047 465285 356258 236063 814739 346740 95704 484227 117657 600800 283263 613827 626493 612683 631558 164343 910405 268718 333993 918851 141988 516338 397210 879571 783007 630063 315785 806249 945739 389726 959291 258924 701100 479411 663329 263997 204288 838394 926909 339434 363282 …
Output: 46

Constraints:

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

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