CT59645

Trader's Quiet Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Trader the tallyman watches over the anvil district of Hammerfall's stores of panels. A careful computation stands between order and chaos. 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 <= 1931; 0 <= a[i] <= 1000000.

Example 1:

Input: 799 180304 371388 312852 160235 287112 588974 978951 895955 412737 693916 295796 935898 415365 58626 627695 565531 288709 555062 58322 349271 577121 605334 941322 42592 133960 847339 749219 77632 359334 79428 623122 38049 785517 792669 737504 207298 67546 172412 706133 552798 985225 635910 635274 799547 958407 742804 309199 401932 982686 408098 96627 520289 675091 602454 720752 468045 495448 336625 610586 685439 21722 934777 629367 275242 526691 693269 732670 373468 648477 402193 315930 677401 400825 132904 42408 250861 143029 825051 646699 383981 79510 655472 112519 591771 207528 347541 932083 135773 298954 959126 392343 486914 716971 223428 21283 33998 228851 596366 907785 546533 699673 276845 590358 345117 761539 632340 57386 934108 815268 368282 953913 601076 821033 110435 657926 69450…
Output: 386819470

Example 2:

Input: 1083 952088 773706 54307 138546 139004 922995 575816 151275 163422 790740 21388 990724 259332 599771 249996 765745 371709 452004 533620 94758 352761 671139 202778 246272 117488 142879 668762 353901 920569 10843 73095 771338 133981 495570 51313 901808 298839 413512 335672 623052 286295 987124 615585 869434 210195 352603 789442 704259 140568 739193 394428 760048 163861 460703 63133 832162 486746 31975 916027 461046 373648 878838 175296 516772 621762 185115 628165 710594 427366 961774 777996 358000 778401 619479 524235 561716 343517 62259 117516 332390 234027 606631 174389 142179 739451 963821 16014 139627 880541 388147 710801 302340 885800 98323 160586 899384 747149 880565 275007 919553 429409 789802 679369 852779 826108 796265 266325 98617 356947 207171 269823 350130 827938 967031 222023 41…
Output: 533647503

Example 3:

Input: 555 573462 710550 264573 347845 465443 872578 935711 988694 953595 151700 917296 400361 254914 468347 929247 416781 522972 866185 591012 323217 312889 170622 182091 354088 699850 557107 75000 816500 509457 347463 123889 884054 934438 525625 342493 191219 7420 631223 732596 297757 122103 174366 806672 119946 602757 894968 285986 440585 85617 609993 104695 653934 613571 523844 663906 124751 317628 127352 179529 126949 903208 977770 456413 49158 50543 677804 201660 351291 740210 266770 948812 921117 786585 939183 631667 229758 821328 966508 897794 140921 614088 43930 586664 954260 309553 599238 535452 370804 618167 251094 408282 302385 635701 362519 249580 611495 113879 235724 721090 799859 308898 904431 631426 162040 934071 325253 26095 551926 2740 64973 660608 573483 216791 403207 632752 26…
Output: 265426105

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Trader's Quiet Ledger - MEDIUM Coding Problem | CodeTikki