CT49110

Sona and the Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the valley of Misthollow, someone must certify the cargo before shipping. This year the task falls to Sona, armed only with the stretches register. Task: Heights a[i] form a skyline; after rain, water rests between higher bars. Print the total trapped water. Input format: First line: n. Second line: n nonnegative integers. Output format: Print the trapped water volume (fits 64-bit). Constraints: 1 <= n <= 2192; 0 <= a[i] <= 1000000000.

Example 1:

Input: 472 651443442 993806996 53899823 261585043 399436342 154330591 860002227 987338748 740929792 558648052 930580122 294066624 788048702 738774639 697534047 634045059 821467271 675363931 465501235 261434626 46330798 684273126 663667290 467135627 282647914 687673091 13729743 853412710 565219425 682540298 621623395 132419666 90002987 251529333 769181339 438017625 787258126 232099396 412041172 290439087 549155072 290498211 600227382 81953409 419390345 845342676 260607638 98638622 601216618 120587791 63136229 420913207 23825091 627140639 270634626 264638326 149082637 666505234 7900538 584558451 885694548 508764037 714334200 286090060 931425452 543906883 76707483 696444926 304541257 323594183 430032739 870011612 636033523 414883702 250142207 520831322 844003990 123320572 293030934 623915561 4026086…
Output: 235286662356

Example 2:

Input: 1138 989110546 717433623 220997604 248653846 190145405 774720047 16730552 69170487 307846488 552775467 87469383 791678509 390204710 18993512 569635174 78424582 552666926 608147416 915124386 742421896 862043046 360185788 125335632 657981704 378786038 629628274 421600852 36043873 92157943 337542435 279231827 373325574 319420763 985778724 566527351 826471406 577864678 136364904 55279359 263634005 977122678 989941861 127720914 588690806 848136984 903764799 958828418 119542360 241394579 544266967 272681518 580745478 356589025 765971720 246891981 601802490 228417797 234636711 983983746 781231985 48657572 870589864 5292959 405599606 43192363 525190682 243937984 25900802 97400366 999848911 639006335 231511567 397728325 450075218 595218837 718733104 19551898 145339249 363670156 825970436 73405954 5…
Output: 568006209115

Example 3:

Input: 1775 494269345 896968778 486878658 713741536 273618073 860071404 614372430 989007871 227073618 501415713 56042866 564306319 299720023 255302858 231693623 119836519 156279351 54483311 103478590 145700847 220291207 668289911 477249094 321671068 334584886 81569780 786936462 679895116 810780928 18773799 519955149 526714018 397166946 134269233 901904343 89371701 394253770 347264690 941586409 998497512 925223807 776534411 922479232 622493074 604321631 984858678 127384882 6541636 86141257 307442590 757198703 444645724 749476348 166751584 467884478 788311975 397342241 323514735 546303572 272763930 425293844 249928339 194344956 857164274 585012953 131982620 741167379 328868940 993490454 605574770 295866160 313989185 462930138 436474387 398973675 935636443 778966773 59678086 324138451 820613920 7865…
Output: 868972283832

Constraints:

1 <= n <= 2192; 0 <= a[i] <= 1000000000.

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