CT61074

The Rain Ledgers at Verdantstep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the bamboo terraces of Verdantstep opens only for a perfect tally of stretches. Manav 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 <= 2641; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1813 134206382 596339176 210538691 893401577 279584579 593432903 466494972 6475990 377803695 55536780 213783745 234902233 909763278 14583043 155107764 344291113 96307753 99453912 886679279 307750429 210190470 908181273 725807149 469294710 255983302 101893547 580407149 970199959 254852707 227226538 587121619 817505651 790775176 885674890 869711166 257976370 798843160 340320415 938119187 126359443 572625125 789376793 796528823 979704754 772561462 660700262 410770056 874565913 950839777 798563251 474169508 320142532 538710060 451492205 869046009 144046137 470710535 986512435 928159655 317663593 397598982 931820919 741747480 338744829 745833153 757424816 84203821 500342328 437526793 976919553 593007734 268824700 81922347 927930176 787189362 927064810 589880038 912242425 464321378 641280944 678…
Output: 884488965994

Example 2:

Input: 29 208986890 577565104 526786581 579598238 642259852 566766174 855940540 800921120 833270135 548508848 561301781 581587721 663934942 465691158 589982409 241738476 908042301 515453827 361050881 806216280 722592052 392551805 640992500 733925322 278558541 535750451 193398603 123084957 786342717
Output: 5948615828

Example 3:

Input: 446 97281290 544898048 842435028 26671183 814549741 780886469 585511262 509367785 527629559 193951900 236964728 196400600 465647620 564051313 733868809 362825710 330927015 344756059 245826891 799610162 890387796 530778894 388455975 488455669 456498619 86526925 172012278 85500485 584998455 735290620 871487599 221445905 154145531 246400238 386235893 919781972 83847958 394308347 355549184 191638617 353021420 680810317 952172179 935545405 181277369 905456 394011983 15199674 442873857 855775300 592927111 989484437 509901463 79333478 289562456 636556840 185396713 751609511 213929989 756139369 460412786 99556255 971612585 237902765 780392283 167319225 866826399 296190992 699524941 527298620 371297861 665827072 200685208 366265417 328364199 302403489 837099009 872305321 582632017 436939066 3550706…
Output: 207182516962

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rain Ledgers at Verdantstep - MEDIUM Coding Problem | CodeTikki