CT36657

The Will-o-Wisp Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Bhavi found an old ledger of panels in the mill attic at the fen lights of Will-o-Wisp. 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 <= 1616; 0 <= a[i] <= 1000000.

Example 1:

Input: 715 33332 234363 47991 15563 769396 954309 410021 628271 871585 259646 431711 388582 888406 913902 214400 799564 298947 825415 569884 489802 351598 476105 763411 101957 679161 557488 916844 9911 438452 334823 667241 80651 989726 395901 434855 611704 382294 436264 117109 205529 97680 840725 707468 230720 336341 156820 978459 116211 790041 109289 319481 788279 615186 405738 947648 268574 951308 941154 45748 283884 501059 639803 438264 587087 524632 598900 524424 794709 586567 545444 76131 438337 34128 982273 747285 312571 117088 63789 892059 159998 584552 613641 285177 447858 445101 192266 738103 499724 777533 775520 611886 784332 894892 262026 982436 834301 696185 96350 674401 542200 763139 850495 509381 56447 800897 468385 998084 753682 436486 473700 202494 10466 109174 378794 43384 396834…
Output: 353823970

Example 2:

Input: 1484 697023 675315 25962 858007 97489 616726 516676 504571 787862 360993 338313 758935 451811 395425 596572 345363 217665 315552 513052 490731 351392 53822 358365 361306 961097 558315 401971 149470 988735 277337 54974 685051 351261 336256 958718 571428 57319 196737 810181 746177 172977 939587 117638 136150 13599 208203 78265 457758 793703 211306 923433 66048 856786 6084 269170 616606 755178 323208 970941 574847 614011 166305 548750 22272 403316 673504 789110 626662 67957 57521 694925 580839 998603 740288 818567 614803 204561 721305 114936 952607 553817 23834 651164 893759 751520 112969 138000 722793 684594 521032 157064 47383 568848 585035 345410 419370 781310 104669 220762 731145 335033 451383 23312 466985 977178 855571 776635 611092 738928 309788 300317 769036 425198 96519 598132 845143 …
Output: 731279282

Example 3:

Input: 460 972267 848862 105499 364647 928834 416207 157231 215607 943532 391592 776129 324264 823481 721020 536686 122720 265021 596198 303791 745863 456895 12286 712194 476152 59196 887187 870472 938891 615699 508277 252469 105230 255770 677068 824969 84177 866309 863479 43791 991292 515977 724148 203620 72715 310574 245928 424590 6864 715715 899331 898002 704338 687977 407808 443292 242183 218419 418530 819132 637250 421928 727441 631904 662330 60823 483298 785148 92580 323575 220157 798994 667549 54117 529879 665136 945500 448595 941831 442212 755240 887595 364750 456259 939019 635785 630348 214648 519039 926625 106786 633692 898217 984664 473279 229371 973936 721630 388112 268476 87710 357924 273135 273371 491393 401304 491433 438652 76994 991349 467498 564858 817508 805464 920585 349366 696…
Output: 219365617

Constraints:

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

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