CT51132

The scrolls at Palemere

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the salt flats of Palemere, Dev studies rows of scrolls entries. One clean number will settle the guild's oldest argument. 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 <= 3979; 0 <= a[i] <= 1000000000.

Example 1:

Input: 2103 217889652 148901901 617895119 81999218 886840517 290766346 848609332 180874764 517112922 435646307 496115842 624848765 242472193 269975450 90969620 479779048 458874651 657860954 497483191 356803506 244065260 470462639 23557217 628905252 123692776 748089178 263855097 250360824 153900379 672723213 410711263 664953268 132478967 131610511 443695098 626815933 159971050 416866370 783695045 367735854 710858252 343920369 806294699 787482645 53663590 212984361 892954403 389643577 780149378 754027721 415824604 584508577 796132739 832912845 630073120 803834204 544624663 293484337 107525981 253684475 565821937 877617161 204176137 90635351 354719267 578730642 436476697 617745692 250443911 682154275 261198687 503965768 123749545 668357992 145255822 920722800 389636309 259624410 417803821 618847887 …
Output: 1032430348659

Example 2:

Input: 446 618628773 904326496 819971141 170756908 23276424 227148274 749105197 48475481 392594426 754403593 110058365 421916199 577779709 88704868 841827870 793729224 460889886 999472042 712723195 118308632 231878678 757891875 912506652 769348895 926099629 302672015 548631626 830823791 162409598 826410165 551838744 568321392 160613950 380426459 218486504 307352044 589178027 243279360 814519781 334513416 388955713 422200170 573403902 865846180 835783665 972327738 178074681 633506285 114097610 148111588 428718841 995123159 397359684 584562158 634203000 232070224 904215651 849353137 482934939 34016698 175941901 321763548 844362643 948224194 648903650 278344223 543818607 174694071 556209516 245709035 595260338 577218856 449371981 38958859 383027584 265966803 505705826 824919940 252328790 633125865 3…
Output: 208800778137

Example 3:

Input: 1879 622395443 147953338 662518915 195393245 356924720 157658802 52724040 684167681 827643687 741810584 266435179 28891431 267437022 309257546 869421960 586083657 224844599 448636307 869054080 822257506 31656876 414875238 434454658 289902160 166695950 248387832 154265794 587493835 152406772 463943227 832336378 929661560 188584267 572653266 43623650 927249022 835741503 990945978 352257488 385700125 80188033 474257053 302921001 288082645 3210899 96222486 789912510 617728897 993310081 769049467 523686328 719416975 990004258 38020893 35262867 215226168 352055168 47801744 365537638 970745741 546317473 586973890 524510408 421437189 135138814 739393591 669378022 604112697 382922299 305919104 371891907 50448514 408471927 229298238 962087240 148044463 844404816 595598839 819491059 839270657 2134507…
Output: 924214095583

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The scrolls at Palemere - MEDIUM Coding Problem | CodeTikki