CT35525

Chaplain's windows Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Chaplain runs the apiary at the poppy fields of Scarlet Plain. Today the books show a list of windows, and the numbers must be worked out before sundown. 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 <= 2838; 0 <= a[i] <= 1000000000.

Example 1:

Input: 174 460390565 314786750 825146438 439359974 60922308 619374105 732375177 646966874 484248062 584892810 375390103 202208234 569729958 699771802 264397376 304368783 493070138 202056546 418051764 486153349 857298013 221898916 410164039 188981842 553367720 989032925 25966003 258188910 985083876 357708227 754507140 113046745 45443018 273084976 948426591 132921184 741564635 175860764 80054842 499340266 208677594 953429417 484138692 896947059 155777820 77606743 827834615 591691578 981977391 913707225 850427963 84516209 955165982 451257262 521562542 873341965 3780107 323779801 970441109 388723416 425184735 601054204 473045334 819760439 985700086 941037390 513566426 12765134 384254892 477390648 787030874 837691829 140067526 442313093 121645753 857412412 397481121 480563973 175243063 408894599 18701…
Output: 79989246223

Example 2:

Input: 1328 697123517 701023030 347600273 277374860 650513861 917730601 118769050 977114573 208908812 733824285 801538588 894016683 71951138 251245740 598917086 163118072 916141544 404350434 985590750 238158988 227624624 451072852 857229279 301001534 830939951 106639288 696359623 995213414 193626183 266451245 231995927 102152880 793807450 359971281 124275051 933494216 441698620 50891412 913690114 800874859 33666665 148662649 86918123 158583498 864919316 465114135 780017782 263666466 750280687 67906515 882700821 579805171 227244826 459509054 405832399 229377639 513190854 107497571 482742864 530234911 773185783 26086147 853942002 825599239 569265889 833078022 883078918 893918914 817717414 820848822 150170721 476456023 893282441 214154015 569084194 650067111 949444855 107056278 445829624 73854217 19…
Output: 656258051895

Example 3:

Input: 2217 340966797 374586434 533394969 232908249 720138254 949768144 398032870 275304769 224112156 616216100 181871073 183619133 981431478 85628687 989384689 955595945 500312527 911895218 712307747 987531998 741449426 356679248 894188065 234040914 558099623 347729483 662609755 678738963 412294067 479792886 535033691 466133855 640986611 994917396 154437528 575286947 883103499 389959857 551266845 43232279 385215214 282646026 316115145 48238751 935649243 510717883 115387201 23095550 519897204 918433712 693192147 829303452 492473906 331883160 230005443 857147832 143293089 14312929 831724036 378390837 967762241 546819719 971042062 570512843 975869868 325916954 166992144 866830883 464009755 239498705 395157229 761246961 181727314 907966299 593290824 320969592 771251335 958129562 84541379 593597214 1…
Output: 1090738571855

Constraints:

1 <= n <= 2838; 0 <= a[i] <= 1000000000.

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