CT64818

Yusuf's scrolls Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Yusuf the measurer watches over the crystal caves of Luminar's stores of scrolls. 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 <= 1619; 0 <= a[i] <= 1000000.

Example 1:

Input: 1081 820870 473548 872373 825390 779777 879856 558963 473918 274409 801515 509625 745131 202961 731514 190404 302303 268597 937405 564757 252127 768045 158216 875636 555675 305155 595038 245914 909264 873283 810993 660095 22260 78754 334125 768221 840235 187265 790017 47076 823850 944116 637757 2915 850107 276291 141111 158318 443039 730912 881890 71352 293233 21315 59022 954716 314803 709408 108667 169424 175939 786969 804234 558227 698797 111598 462720 873909 988027 330447 92929 413700 634885 392937 363009 6092 964156 45052 56822 275426 179692 882066 922684 650281 94388 874918 981393 672147 44425 119102 449253 97594 921242 833921 543016 354178 524671 114214 990664 552388 42012 791025 813033 180181 384230 153456 325806 798139 547146 396700 46209 207980 923985 439291 791752 190334 534584 7…
Output: 514507866

Example 2:

Input: 51 910483 246611 114101 679267 860617 850464 657197 467512 95441 105205 258799 575935 78938 624949 313495 568348 257949 197507 28803 398173 921434 183827 353120 769355 272788 80053 634147 776015 281894 983800 246868 373183 2514 122586 127379 182331 18667 110346 379361 510818 575503 263905 303373 97078 862736 324232 592913 513581 124989 467783 63348
Output: 23316006

Example 3:

Input: 1399 991687 885334 972443 431716 910147 893668 682091 650882 108131 185808 149202 725227 107020 364297 822591 769617 465018 919466 669029 493922 416505 213727 370352 24561 182243 982974 222883 538571 47000 153796 90443 795792 474508 308175 525055 393842 108085 377369 612650 303948 804659 817129 223831 130417 142628 735356 566782 540605 97764 293558 811084 135065 986900 182875 978049 250403 264991 69550 903899 134209 572773 697945 658636 24489 288244 810535 127225 251649 461002 450194 152372 338960 164923 47807 975418 859425 705641 909473 670398 518826 806220 538949 421728 851646 954933 613320 523853 134901 959541 898741 850796 162171 812826 497986 288525 48319 381751 717653 262910 639034 276471 458775 880126 392315 740521 439362 31300 549040 940250 134047 527094 828893 480508 827909 309704…
Output: 674591040

Constraints:

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

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