CT63220

Radiant ribbons Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Grey the cartographer watches over the archive halls of Scrollkeep's stores of ribbons. 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 <= 2325; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1112 314614928 532087623 742806789 604914344 865541479 152614701 801124983 196077428 195265759 97499944 887999459 610640803 467765293 718231278 49673768 546611905 623046703 654338465 845418429 819388237 751650022 322973267 894569622 875835800 965781023 3165529 172737705 337031954 610499166 636348854 595139697 79835980 670349335 764787455 693998178 179291202 917203390 849847280 141281658 611077101 165029765 779400586 845330319 930630690 131493743 748811845 800545234 647023967 668961335 516521401 112003353 211791197 604963551 209132313 740933125 163578159 670986797 123295348 233296341 61443302 180005402 872628197 989867245 108749082 150630089 159401581 397157706 25659807 856592882 500843902 537634448 501990781 845008224 157691452 632219901 150761109 191602911 850988595 719128929 597579770 17…
Output: 551113621966

Example 2:

Input: 767 524309865 933374227 556474242 641070297 31453471 641795484 961172521 886975833 891228376 724145194 44703242 848299708 498868729 439331172 767769972 701470097 916496293 522378948 343348204 311161373 321157718 248640374 582006729 989513375 701179762 575549070 237719884 834454699 172333301 165876146 688621475 382939122 704392638 144294257 492611861 133672762 497509802 790760332 221058639 833595313 94645169 89581683 117092552 982380261 741747261 606597255 182713241 199715540 102742235 761002768 855014439 626732239 552878226 619518777 973372941 28759149 377597200 413001173 432826235 190848816 476767277 593848092 131490536 44330260 170417894 281085459 782758126 574901406 314740147 360422957 188230262 305839167 738112577 326191111 281846856 142814181 677359231 809421869 650580934 539714677 90…
Output: 363934763116

Example 3:

Input: 661 536673728 251372875 330922259 251561103 251210530 153376504 347763481 840359242 697717018 935502359 565959985 444439110 199045062 423880521 220174044 302188364 953373217 420444733 545458579 802326276 66371866 440363476 949367204 566175014 547370553 872131912 858142059 772062799 167548376 938349089 686132350 719224010 990839987 750147767 393499490 933608561 815711270 219293888 850503194 862150753 92780024 503605499 865455493 958427988 707015415 6965093 411121298 936267606 350185584 56431623 88497657 349580384 564315755 680669785 832092642 770471231 432515771 416692269 866717921 281060877 7120887 812715933 821645545 224829335 705626392 541608198 823318556 528940782 795389780 668994618 655575956 770509435 312595016 3178966 401279041 438580678 827810218 122655550 385944933 833964824 515035…
Output: 325838541506

Constraints:

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

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