CT55769

The Rain Ledgers of the Windward segments

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Jace inherited the foundry at the lily shoals of Padmore along with its curious bookkeeping system for segments. 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 <= 1852; 0 <= a[i] <= 1000000.

Example 1:

Input: 1087 107162 579049 451775 536614 317697 385057 268628 743793 375969 386900 279586 779261 964239 816460 86790 392334 222822 182577 466584 484359 25101 837256 625453 640361 559240 546710 461558 137324 18967 977403 411172 107580 947948 834382 133679 260436 252691 616060 445397 243718 855742 892866 204889 685229 708726 933451 872051 159907 19928 698063 42826 300818 347292 972778 376593 225266 862487 960353 480775 202458 979749 312829 172997 530153 50684 979249 86520 689409 324378 308421 241907 539412 884026 796618 127968 797587 896228 140623 129111 447069 957650 208701 245826 297040 539996 711886 226936 507682 383818 717486 733512 896826 342820 419072 653541 990039 977646 725118 400840 891783 336845 523717 265600 404654 423083 17278 684625 410244 453049 95418 307896 175618 524880 553387 343313…
Output: 537072748

Example 2:

Input: 460 173953 205033 660199 495914 485459 430805 29306 688432 659296 745857 157200 999323 994429 998624 70635 229993 178128 474952 941479 276056 185993 357818 206080 181310 652934 945840 66811 578761 160270 817625 921118 385403 248354 721207 773761 428547 383606 962867 547604 779285 844724 377372 415627 508564 162667 365170 185101 867796 963029 847599 722621 131894 188477 582873 528109 671821 207039 495067 903106 430794 272862 834212 226975 757352 492473 159239 263652 589986 710764 579278 312367 662357 685129 773935 479857 779026 399555 623326 664655 648893 547033 173842 322290 351536 720118 184634 266274 536084 370576 847308 240353 101417 743252 817444 874775 972213 981225 800752 182705 535644 628130 262942 104494 211680 38302 271836 162681 279124 844708 812969 797391 487112 490314 337607 84…
Output: 225336962

Example 3:

Input: 808 459597 34943 677851 696630 313969 141146 166760 915028 62003 724669 209529 996425 599752 405717 282665 579638 691193 885749 281924 877417 248658 39312 644946 51528 918998 993594 206079 78894 661180 829615 731620 304913 292964 643698 591632 840583 64937 488652 249136 68751 382478 708040 996905 82054 544969 894444 545759 819871 291557 263507 553384 849448 912678 615555 647675 446358 235266 939016 652556 401081 302685 435535 942981 885167 93388 319041 909624 498716 43214 963749 476186 48010 985964 190211 668780 571809 382654 323303 813500 75351 419786 262544 802490 212524 731976 704460 616873 844413 74777 436411 788991 227878 702045 851277 979510 793293 413552 721828 359352 772377 294211 953198 441552 968312 585269 483488 487538 771367 303117 406916 948928 250785 87483 733977 770468 64665…
Output: 375743381

Constraints:

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

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