CT47926

Ysolde's Bright panels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the jade shrine of Serpentis pays by the answer, and Ysolde intends to earn it. First: the full register of panels. 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 <= 1490; 0 <= a[i] <= 1000000.

Example 1:

Input: 1063 647790 233654 779998 555922 461896 589096 634409 491135 162842 519699 832497 70408 197016 43075 204412 787470 773173 97111 662108 10900 759465 424022 285513 572344 195433 41730 58509 52573 722566 749235 234218 576622 445394 524340 261953 565921 502988 539704 87007 79638 149204 215295 982571 384094 345023 265961 938011 728600 981379 759653 823079 490794 160086 322017 466397 741566 437502 649372 406537 254581 755728 686992 62414 277461 403635 156285 975478 13552 792033 841854 796041 137005 107448 885154 290623 657750 759082 341964 713683 748945 46684 403177 287728 208106 831167 207496 804606 48376 391317 919141 356070 661288 770384 794142 573988 349495 783977 615658 8762 601589 587105 503379 619954 366832 684222 989804 378441 863479 946505 880617 350883 985998 79618 201413 910439 159632…
Output: 509228476

Example 2:

Input: 66 271031 724028 943853 539506 561864 502782 6025 498557 794653 351131 44730 905681 188367 981332 39680 506892 75002 446326 982265 442679 489395 984950 436254 111598 237044 531431 999247 731449 36265 983402 20717 425275 122519 234142 69738 108689 158220 870577 427990 637553 691077 284424 11680 138785 260170 405850 894168 963431 167117 111525 815287 40789 295661 758636 273756 557070 50831 938056 829995 583570 343674 667193 522369 166546 321122 512373
Output: 29690486

Example 3:

Input: 315 676 473831 204410 111998 119745 106079 184812 253805 908997 859978 470780 798050 254149 297404 906564 615167 551227 287532 123255 995429 209499 255034 321103 348885 485637 705112 467056 425552 925601 271870 451705 654120 680467 877757 17229 155427 680996 230350 152511 277226 697118 304036 697313 979907 431286 517066 149298 397488 485351 485387 628562 343656 563444 177808 901272 777197 487567 189037 179402 770393 498122 576787 405805 320347 90126 956069 160360 53538 735014 605808 970477 75619 222909 382046 802780 963695 66445 675401 802278 679816 875971 181107 873208 370699 620405 828982 674728 938073 722999 556760 272802 784764 153968 431873 217813 99308 180691 946074 901682 902574 760564 817482 577725 354584 551322 382161 509010 581560 273981 104598 689738 446406 62586 860975 119830 9…
Output: 148217514

Constraints:

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

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