CT58237

Yami's windows Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the lantern district of Glowfen close for winter, Yami must finish the windows ledger - one figure at a time. 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 <= 1341; 0 <= a[i] <= 1000000.

Example 1:

Input: 314 794790 959635 460279 282924 975205 950969 141824 453299 883138 123970 10113 511524 926578 406042 8682 406771 79934 868255 423780 411365 692739 818216 913371 515611 685994 6606 454919 244168 490 349313 758180 520674 980360 302661 159726 644191 276550 677561 268861 619115 55839 55971 196309 987102 641472 946842 990785 711659 288033 809703 225201 902729 205040 290844 409314 369987 42253 829632 866137 602395 637446 435668 65584 57197 690863 719760 576558 765482 226386 528922 358789 866629 560328 274512 446551 614540 684352 76490 117627 579962 902155 496370 302075 577789 856802 322799 807633 992040 98339 857729 240106 246188 889847 112597 985018 426966 100507 669737 39331 9947 572094 309002 43816 609626 759000 825114 93325 68861 88464 623178 248490 247363 720528 517068 562546 941780 913758 …
Output: 144075616

Example 2:

Input: 44 441916 3288 784271 409248 739783 476570 798522 570757 678529 606174 470528 830033 705747 672553 604906 342244 379930 387242 684727 975550 869613 417825 419592 103749 941921 717565 229463 392086 254110 961823 463057 325348 248915 171128 665517 731579 13458 169219 91683 73122 959336 652609 970555 989812
Output: 15661199

Example 3:

Input: 1179 571936 742705 308392 541479 259193 681521 166632 377643 913957 615423 106293 284331 678549 67214 497757 962542 235321 850757 544718 149304 140482 822063 53904 365680 481928 184124 314813 494035 894978 2102 733809 327827 225130 799987 997166 2340 380426 157898 836860 166008 911811 325286 795588 155707 535015 606669 63112 764907 330036 86943 932154 96117 26093 518701 652101 588691 377171 16974 313798 926681 815431 307578 889484 760825 311576 282437 831103 515578 300139 735968 210399 497074 98988 181615 990538 101365 212133 747099 932011 643775 236984 968442 694468 196555 378744 50169 224651 985255 609518 224397 455384 400024 222674 680819 914920 893734 187333 518878 67889 531742 630773 387959 278240 870327 126147 8201 175833 180143 306509 167918 329449 203171 881482 387546 982618 430129…
Output: 576209794

Constraints:

1 <= n <= 1341; 0 <= a[i] <= 1000000.

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