CT62732

Morgana's Rain Ledgers Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the honeycomb cliffs of Beeswick opens only for a perfect tally of windows. Morgana 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 <= 2308; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1886 308208541 859678190 551773004 504824664 747109301 890230896 931286872 412980433 69784290 5236828 559451332 989421752 803704381 453176369 568415104 999532642 109039149 111594305 846342460 413304096 982317385 696787235 487606420 619808844 261337413 193613034 45765887 461962330 22655252 522190477 666720229 3581104 556959012 973213186 475283684 353119013 673066963 597992601 946751455 557717205 903158883 129094112 938170373 944504659 169284650 480544807 508465718 772415250 154736681 821449739 301199089 306333064 460290175 722152530 487986946 750211837 224456809 885151655 992085926 613407445 891457258 279423568 957246526 510587614 616089415 933372111 328843745 134152236 393810200 337947403 313030883 37098111 366794792 58556366 266421953 897394610 100273564 836863400 483123682 923758251 2758…
Output: 908771669635

Example 2:

Input: 713 398168412 189697872 130499496 934743323 494360168 764305995 824027912 926002851 191871819 998267789 241925991 748080082 824567409 234350168 488838006 851524612 663389217 992108043 67616864 898114 371931659 625694858 7526335 34798787 486960374 432876935 528009652 320354894 793039407 300741501 811995671 102045278 65792400 545548112 930138561 820679532 45835739 172018997 849479008 524892699 660574344 570036221 913637420 584459486 775577766 19834565 431308879 166685824 444007942 192740508 242351279 593330205 591606547 611175754 733323393 325648598 124576271 774017466 211256336 35926611 532986625 708225328 183349889 123062626 989871482 297473828 751655756 824067779 323449431 932463470 230011242 337781194 785654525 981133833 806181229 450867765 624860062 232782922 713948390 843127625 4919041…
Output: 338405978771

Example 3:

Input: 2210 590752113 729847818 692393586 541032592 5089464 847309813 522143015 770316805 48233793 898745045 971458922 293301221 544741087 694116473 314634738 243289157 572274513 302609652 85623597 198507629 356205149 997016562 977044330 715543221 348794155 547977017 797882435 590929438 572684521 655354167 939787232 736665588 94749806 370984955 412763997 985029317 995253016 709253189 59609913 102362514 573894963 939203143 472188353 322071936 39979628 332395338 508173221 188169872 492412200 362521711 242239868 288221440 311153310 234028041 788890796 444702372 333937975 536203995 291205247 727508432 873796224 633087963 570333379 601597977 558891613 307721067 586856653 786735112 98986501 796769647 47656601 488002485 439039902 649780543 845838301 503234860 434122927 283298267 404654904 399822788 9582…
Output: 1086674903619

Constraints:

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

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