CT51163

The Echo Dunes Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Sage found an old ledger of windows in the depot attic at the singing sands of Echo Dunes. The margin notes pose a precise question. 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 <= 2173; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1229 888976183 263438198 844468786 786740830 192258271 53263684 368750819 478662631 745935441 598257887 985139195 98306338 842015072 872411371 712700041 479676128 249481431 728902811 617168881 120195319 179204236 659690174 27843766 63210529 562734861 526520604 84854393 189992750 52398856 402394350 483789860 54652351 93055981 555812995 892747259 649514050 87010465 973162714 377014753 924829370 58391356 80118087 730009177 992249109 365812195 98251403 119679814 128720389 70210167 189560863 553710602 748775653 765789812 347360200 867267594 770987939 257198257 247788598 211878688 775877542 515051123 71275770 516432859 365802289 163350261 872887321 50786098 749640240 630541338 318626462 104809499 475901047 24616231 807955116 647022991 293189408 323945657 26741720 780436130 168475091 736427737 49…
Output: 605732050870

Example 2:

Input: 1437 730945462 707445268 955578509 181477530 248928172 543601919 271074022 444130756 329771810 639286595 162760711 839969276 871894134 414788503 684148782 768713570 464857354 327111213 957733808 9337386 128644598 687410428 304980072 334333106 791932081 401167924 445564451 943021174 62230504 29539363 967053878 968474492 708292031 245860878 35856488 56616056 496402572 378707122 393325832 419839277 936891813 286128587 706424934 931939326 123228893 94154795 463319828 260893783 506522793 598387077 959199675 709135548 647056647 520181007 237227731 892084134 687609071 350891772 921414001 66256423 964079342 85115078 259957854 204932404 968735378 397891504 652777113 902529567 124590676 84036840 680816038 993532605 636535226 765470454 551072032 511943190 990057891 725408235 295327884 851541474 36125…
Output: 716858407274

Example 3:

Input: 1542 859552366 906984008 284337615 418014250 579630956 622362829 726054070 490030167 129829181 153844000 45003199 163587674 987409938 791875487 161948553 698089123 268285182 962632101 269965940 411011220 314847779 813983504 882164653 661599812 716055390 881310759 106380754 311032554 480832446 915679796 50644721 794146818 499180842 781263043 403972735 766151527 362665098 564706997 508385049 537961292 428259381 963058629 126228233 909876119 625189601 511095677 361437340 333563014 492901413 104083028 214557127 829143822 799558625 338882260 755918867 344189872 196346459 589726930 168312805 685369108 256111319 355939300 190016917 551506537 552153727 506992604 490341034 963109975 818273628 145510463 115351138 550575560 769361249 734406731 294561950 625493704 319794443 947992651 134084529 8106085…
Output: 738083955823

Constraints:

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

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