CT59646

The Rain Ledgers at Prismhaven

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the glass towers of Prismhaven opens only for a perfect tally of windows. Wade means to find out. 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 <= 774; 0 <= a[i] <= 1000000000.

Example 1:

Input: 674 454128567 943695646 687010152 70683024 373404631 715542795 252918354 642909794 282968293 101921075 288499268 746667449 783323785 222863526 496118087 719709009 958058528 567976973 335545239 201828840 95595838 397884211 754241526 217817827 730916441 911461749 586349905 302728937 343147945 861498635 423964967 71086979 928930442 894649446 10137197 740731121 623528413 675189519 942878964 439518426 398107631 958809819 518616110 624086303 92353841 249221338 924427851 192032759 843600011 641555494 831908492 983196434 854238479 873026364 267500516 466330790 315591932 529625246 976968682 9581618 495255629 161822542 203024477 2831159 859893553 136899618 469598312 871420315 484380890 253170676 721671051 909041505 309721789 572335298 92860677 451584618 888436844 59742990 795565951 898580257 7588576…
Output: 328759098985

Example 2:

Input: 154 579986285 750248871 412715176 123769249 837432245 44844461 375473130 646986246 942134796 530904049 635771662 620578546 495120883 648193220 586238850 358423068 129042770 489715207 94516155 147387344 229699675 924302703 17686576 903446539 530994742 682544723 142392431 697523878 158638503 570199197 187860773 800305995 836156448 404032263 659557608 513214784 691478251 424973074 945025872 142444879 87174859 742850715 744936467 789720377 609936841 778321726 364873516 393045611 475297626 968544033 354274703 657392018 705641284 994063553 771718656 496069165 978063223 514027849 906933719 213320149 42623420 716346163 398524992 173305521 462329307 339919074 674745532 49672569 518667971 477362559 300585464 198726778 653061752 120610524 68554077 239085756 642267439 199135405 424583328 956341659 588…
Output: 72228216021

Example 3:

Input: 449 401057596 174105866 833363242 250214429 909974805 50504097 310127031 480946836 360079794 173484878 888207433 151439959 840677583 46808693 582452891 929596573 744662093 958888814 237678670 717707300 79962698 904586900 328289370 473930596 259998800 961778473 68946190 62841199 758978237 150392264 219914917 269217921 451531277 213998529 117309321 37375937 597651906 911608382 843506161 563227583 633234326 836467029 409419246 164660081 999532811 709042761 55724143 947733366 353120067 674587359 632901624 147017634 581392831 539039010 686992536 683385773 302077651 710693284 815799646 693100673 792755967 434447217 887374502 772176275 976676984 102381790 467063282 617129948 310080907 14626398 861611344 188980591 260330845 860796612 467680661 265654808 637134122 923401471 379673075 988973404 7430…
Output: 212842581916

Constraints:

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

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