CT44250

Porter and the Tightest Stretch

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Porter the scribe watches over the quartz ridge of Glimmerfell's stores of stretches. A careful computation stands between order and chaos. 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 <= 3047; 1 <= a[i] <= 1000000000; 1 <= s <= 10^18.

Example 1:

Input: 1596 69545271237 62994384 966212684 562081452 692924855 123971768 918852264 528967543 748007782 596742351 962629642 879474392 965123410 384872990 52659077 659836147 705789704 374025515 502728431 321304598 334611399 858207594 875389207 673940808 562857836 739343309 615784893 906898255 726975999 49503898 622231140 656335895 988126253 684304674 445419851 636640813 925546601 704421345 184129719 166094678 593024832 202485160 136449904 206455495 270291457 767595867 159305366 864605830 276847467 692431975 434896900 479936864 810027724 450689493 212823544 148991875 262332630 734604193 24375289 76950977 935444850 43287464 541791227 662259700 196804349 390876573 196613647 925640781 133742210 323718101 363680736 386669051 35705993 58001982 951783308 899475619 766103255 845715585 998471089 820855985 5…
Output: 133

Example 2:

Input: 511 52681342435 1664970 330567205 453012389 288543443 750393893 72606056 79139186 925688201 288086994 530882510 408999944 901690633 702700944 765947932 419790643 329645571 456994192 532622797 472228304 301294997 671714491 883428355 418667050 995507055 186954379 849893618 315926920 28115444 978325804 581003395 43342050 348599166 435886186 692337320 427725498 872916192 578501229 671594256 219809990 798097574 774700257 201278338 369189738 531520888 692242300 136868521 526624386 314573179 580339045 407551812 783443848 870837110 394498678 581193296 179324590 743764118 766303276 581723422 169742251 740232926 78617229 275226552 824527607 606024722 82661887 56564185 490442931 652600450 471240267 434501994 371476913 849822078 278215886 8245383 204998775 753317495 684933150 680794751 875072911 53942…
Output: 97

Example 3:

Input: 472 87039996658 896301919 641827381 859532087 655565928 617270546 35338687 420694567 253648190 972663604 626349629 943236001 988263817 475111355 551530760 311403190 763879265 384241406 165913943 593336991 245051976 825740792 259279450 974913003 522076404 236046423 424632169 982793624 45556925 584511765 152722323 385347179 399446384 930468017 130039693 667407003 400858029 321675521 749347008 208598169 145761875 456544644 454144337 403493967 862547476 114288968 816857177 133611024 552178053 988944409 49763930 651428489 908878974 203994106 366665770 430051557 853058980 36474522 483048505 799654966 185276477 301367365 762534124 748304462 915528177 397201896 715119681 810790926 549535899 1095691 350547516 133544719 719629238 369967555 625323173 304582407 434363121 544047920 216369468 438521223 …
Output: 165

Constraints:

1 <= n <= 3047; 1 <= a[i] <= 1000000000; 1 <= s <= 10^18.

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