CT38083

The Tightest Stretch at Driftwood

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the quays of Driftwood. Pavel spreads the windows records across the table and picks up a sharp pencil. 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 <= 1785; 1 <= a[i] <= 1000000000; 1 <= s <= 10^18.

Example 1:

Input: 81 28907070566 177101871 55989062 395629133 666690155 108275404 208501262 808188548 827043553 470954257 439723417 590915275 191339864 983624616 16882267 621469679 243160214 318717190 340694915 983653284 193343104 941048397 677910661 911762128 817457374 492950849 172210813 127280349 847584389 525987417 451986967 523242106 955159693 501170983 672253026 473364854 603214578 76466723 486363075 649422101 708016026 214409759 36591727 911563447 967528996 97409701 139903616 800330327 53949905 148177362 637664968 820801672 745757727 366855343 876635947 74625218 20616671 161661725 637738353 609268205 400707698 215683631 387505603 32047243 802954141 385094430 312680080 941847296 541137195 683049519 588281276 119712800 481325671 529322159 801840461 331183749 819957163 600900884 221249659 173288325 5604…
Output: 57

Example 2:

Input: 459 2844656266 499461577 776703186 330238443 963420881 57941480 864387857 404274360 703007292 948365597 203777193 672624493 304415482 380654291 42139278 251324715 917958418 159219269 603458926 624145031 89338980 549209186 861394826 658354634 721385 709768913 797573198 14563255 143015129 478748451 194412871 302059255 770690592 722871105 933708702 516449804 889032475 512172546 696034619 783704566 202432641 696722028 871717418 223215193 257965917 381776753 274735992 135447869 790427944 984123366 242808447 10365177 858426998 913253158 610118019 686780780 80805926 188990158 703719080 967417351 990883747 256821521 825322136 322510416 225049643 915213455 261520254 351515613 868406549 968339355 657597647 6459819 603411593 612823434 554113749 233853938 188863138 925235476 931384314 591130684 790744…
Output: 4

Example 3:

Input: 894 38925722560 665599743 205259544 801844751 764538562 363719670 977038332 622699242 394449643 333799335 569855167 177356545 323456017 233835775 230294553 26303248 769101272 822607995 959580457 422806770 298800623 869581788 151598239 663027665 560781123 231083481 563512979 834237515 418985041 221712165 889200714 540289749 176502452 234728951 567768351 460646587 840387302 627143008 990511636 156806606 95697418 990228835 973975002 450073270 195442623 375411538 99318158 259478440 564593314 222267999 70049498 95854706 406180243 786634242 787593545 904926864 554157750 210358324 493115833 682127908 835077501 506947166 561227368 324580422 668024030 930466329 818577508 245183520 262694602 453492562 284343168 664195199 745802526 806114833 665219268 786920817 38483443 94139364 476329940 107791337 7…
Output: 70

Constraints:

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

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