CT59981

The Bright Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the peat bogs of Mossgrieve, Shepherd studies rows of scrolls entries. One clean number will settle the guild's oldest argument. 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 <= 1384; 0 <= a[i] <= 1000000000.

Example 1:

Input: 650 143265980 4576650 72340736 55823610 466816475 203323463 852898135 641274734 7896344 815773748 985536185 682823936 842022920 985529319 507842241 96073314 51546748 610260489 248402683 645242460 644505848 861118851 840716254 449742190 95391225 827743073 749506928 922654918 903206109 583038293 847671496 497481496 500784600 119753856 388131394 652819895 525175474 140362041 672930274 17063383 166505920 956212563 969864952 564291079 544982689 501315844 589205445 836431377 74644498 739664680 397411332 850137529 922171732 158474868 306544670 367336856 141136869 915157958 917978408 72226973 129199634 826248967 979467681 912805323 523343382 719242690 720063849 864356403 461546841 337421660 463708768 119717591 227869696 345310482 255522004 929323754 872316468 399025187 392617912 616011185 89146024…
Output: 301059496398

Example 2:

Input: 728 817991817 25622330 922710125 121405728 429327504 486804530 70528503 651678127 770987290 847863544 139611992 815494565 17895778 503578938 166717396 497849046 142246055 842656717 802230253 793507550 959230277 688823010 352905863 911080026 787048775 490999448 205308529 317800934 81270111 142004876 146776480 374766234 661857604 570130724 711312967 56116970 866708361 834599271 906131516 522267979 679928582 786332706 737671021 706560620 909667552 100087962 441428915 643206566 417498819 120053479 57580958 249599726 977972459 315365529 307485470 941912844 735939077 78316038 878741667 359469498 289486996 567728505 199429288 117317296 884836972 614986292 886788548 617660115 465221598 970894065 769543887 14561618 623697130 479964168 259421938 459397721 604380386 714216520 691867785 377227918 8169…
Output: 346264565766

Example 3:

Input: 1133 164751380 929201865 15279918 595860989 210734185 883033588 774121925 594658271 619418149 99977420 1617907 472543468 707640581 672215473 144268271 815678278 260631937 557804109 480085544 636374029 977605270 108823233 812859329 135585886 548060833 957010689 569970246 626501845 478046130 926976456 495951033 407549000 904992440 411440055 867581847 976571475 623939624 246710458 475757241 378910784 887401232 714923623 106433901 444342842 518503912 852666150 838437424 97707954 737002408 647248157 350787185 893895718 901315585 285523329 660503116 93392681 286699889 167173745 134616572 929143758 9011271 976257380 914237962 653018859 882790346 240502283 286818213 47717560 423740972 300440773 305122637 842152029 165536057 665129469 887368098 141773773 518678803 936457310 251499827 759329476 3298…
Output: 558123811215

Constraints:

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

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