CT64129

The Rain Ledgers Beneath Skyharbor

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Theo inherited the ropewalk at the floating docks of Skyharbor along with its curious bookkeeping system for ribbons. 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 <= 2665; 0 <= a[i] <= 1000000.

Example 1:

Input: 626 344080 887710 599736 30469 752391 207818 200076 401874 28256 584136 335445 979730 961853 62190 354983 264304 797064 820926 88204 79776 679099 637426 129030 672218 25055 662624 14836 814314 670928 839587 364727 93834 14219 989989 357662 659530 834972 403212 654250 954903 943004 463728 732442 103749 14928 683917 506915 563406 807592 751557 501571 148126 4500 222156 73979 696719 658293 575384 873836 550368 297959 322065 780752 995596 636092 280848 41127 993379 43246 505586 957346 431933 847863 574521 641313 927096 292238 722428 182374 120838 644214 762473 569574 731562 383794 666423 712257 388558 862458 716536 438489 861573 953364 247141 520956 19344 64434 55991 176884 457020 406301 54124 163840 798457 505418 11974 526110 958901 752463 851908 198901 340865 376186 240211 890286 685172 1095…
Output: 314462925

Example 2:

Input: 1417 23223 618332 873843 746617 756488 469074 667532 425764 967721 115053 535600 324926 708188 260219 80895 825177 373880 289685 98286 108178 435106 221587 288613 445329 450614 445058 996106 476793 865969 722906 791410 268514 668041 18622 739397 9105 90293 499500 589491 595408 191144 791445 719355 534722 289318 974126 291753 699269 46492 935409 115101 966777 295623 252594 832586 593851 646775 334629 181408 300514 858801 709824 691693 208487 403444 870510 677217 107155 462113 916637 318836 135830 356238 921046 995653 573370 122315 283632 841103 681671 448112 232670 190052 655694 111690 988167 170083 119334 889738 61459 220999 400692 655325 11451 561349 373222 222644 116719 495230 800065 43822 613982 59315 568470 274443 501502 698402 688221 497862 417531 300111 190249 199389 514403 211816 42…
Output: 717262551

Example 3:

Input: 767 598581 342728 125586 305165 617745 705287 291576 234807 697381 223889 257172 616727 114777 454351 983270 191169 19865 5614 212908 706568 55336 297423 72206 545911 249790 750754 382556 307883 311779 596183 56806 35344 63403 452839 334002 433480 61841 404920 339519 349333 144630 412888 439290 56337 391943 995237 215282 510045 830813 705051 142211 529111 716057 837681 440928 310226 266273 60239 555583 742663 460199 423847 977389 913713 262203 579242 543230 216979 256029 657888 737247 19515 32362 995325 631696 233087 364020 618360 642145 582984 320811 523396 750076 74937 157137 131184 933963 844669 162053 123226 136763 321093 461496 316008 447597 856589 814167 77814 319775 596861 169421 286236 361378 477486 244743 607662 978127 946800 478497 948136 680376 593484 285592 234916 280495 397784…
Output: 381735858

Constraints:

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

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