CT58408

The Rustwood Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Odin inherited the greenhouse at the fox den of Rustwood along with its curious bookkeeping system for stretches. Time to make sense of it. 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 <= 2170; 0 <= a[i] <= 1000000.

Example 1:

Input: 1176 8352 860553 627227 7696 970602 726100 168000 226382 291713 889672 139662 494786 743854 918501 101572 697718 78509 554418 28125 985006 494778 144415 623294 242135 838691 775126 80567 195044 683746 472970 331673 434438 162520 505135 854500 963761 199034 284437 580824 724005 765865 467744 824025 464538 75224 115685 839448 726630 149504 643217 745357 70708 530358 280702 155731 601098 441932 202387 791600 506280 686805 212672 670916 166707 526263 779215 406983 283330 147845 37250 889559 904560 876378 104463 809353 724869 293231 120561 459857 886939 697612 764202 276487 520768 286575 223354 161798 851336 395238 583821 9073 747203 555681 898280 138960 690230 832244 44390 434707 186579 842129 608597 109078 291003 147029 934445 923367 198279 537945 308769 880948 762391 410100 723137 988312 899…
Output: 587366159

Example 2:

Input: 453 19634 221734 759304 255506 700614 987606 946358 345721 192761 689339 32440 84629 72637 162466 860183 465615 928944 930372 659205 304178 807634 189684 44137 107854 714384 75659 624391 621642 608386 895064 983364 658246 100390 763202 862323 646850 259827 967602 673948 103710 356978 236312 366269 315252 117284 297699 408334 793065 951083 286993 489815 738489 814088 989999 14350 295685 699820 468441 571136 24344 931627 564717 322068 384854 814400 681672 582891 891990 835428 406825 724947 619741 536752 918026 716552 132948 143604 705530 393111 605396 516734 434598 915876 234614 5960 264401 939326 832833 353587 953900 11026 189654 653656 377674 7412 82401 493514 411784 141395 468661 411491 447857 34038 203227 556127 891110 644362 605644 132926 187581 693927 518376 191286 497147 683353 424535…
Output: 216069098

Example 3:

Input: 1322 200658 691722 299294 526638 161136 292554 927063 568930 283745 163422 531545 802975 215020 440764 34265 996837 729642 415072 947651 202718 242002 531249 434762 692454 683009 812586 541569 880333 298736 497768 182423 153814 51378 508384 536670 868333 993827 397333 848090 281856 931367 355325 390360 907513 608955 535448 824926 933733 144970 466238 349003 614078 920059 115814 877681 251915 718985 55950 819787 346836 325549 692822 551313 656015 456731 385029 803098 568812 359562 75122 67375 355271 82731 135091 948782 871439 964580 491974 400489 697554 794014 321353 494250 504564 325610 458459 88560 648323 940515 255092 514293 683851 919442 123390 963139 975695 23857 5105 202146 542790 71530 393238 660874 708318 712221 720282 718581 697175 309896 999591 638796 571253 615523 937963 624795 8…
Output: 654888563

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rustwood Rain Ledgers - MEDIUM Coding Problem | CodeTikki