CT47994

Last stretches of Ivan

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the fox den of Rustwood, Ivan studies rows of stretches 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 <= 1808; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1544 96561187 477339542 151905373 819971030 925840189 837832406 713105716 929111302 72542959 932000788 541229631 365885494 632527705 33261646 65150827 236089084 41657583 905157369 118105104 947845781 837370484 222708154 171530788 175009210 464907407 269189982 549997706 542734803 827877019 951133717 973729282 499805426 513668125 750910376 127950835 813945388 160317571 714430388 990755214 428198097 549817150 688577320 329777916 460408207 325358791 86930649 11938683 991993779 345504010 728565764 787875301 445289528 107719752 157548580 188258417 846863149 847920374 308297454 118267848 463394834 490577804 326695046 74742325 779705632 800267636 814757140 933178433 867443972 183521589 543523189 494475886 862168741 863932112 274816894 290287904 713299991 722272773 916292181 871376265 503459178 658…
Output: 755686657496

Example 2:

Input: 1172 280506711 716660769 349338478 831699236 945676119 888818688 277117446 284704633 877341270 43043631 915931763 140290038 835690948 220249161 514072208 115624202 181189453 559947029 483232874 439830160 776382497 327877722 129001616 297409269 439996825 425566769 424134618 551146408 7232783 445780447 80387225 525539593 335754686 93999960 996724223 60077969 594449648 910056577 175528866 944572097 387581413 970007689 787624680 948635861 694495131 955933557 270106081 72789294 117670940 996053542 274572169 136116633 62483065 286025049 56740107 625147875 207121002 110630211 205832771 127612081 950848662 118692739 62567240 882379127 781594594 795775517 952154883 762923640 383703888 428904590 554179213 638531125 521102167 935876001 390877418 120670094 439617844 176466678 352655411 359237091 88771…
Output: 584637620469

Example 3:

Input: 771 825927982 647825870 103713018 743084732 365466030 243154077 106837777 890847327 957186808 963323260 419850031 699224448 608594978 949845489 12444884 660410097 548111773 185978919 632468932 128020428 695886688 67890731 459840523 805055745 674766766 65427617 79124323 102705357 678533976 594256429 746890464 672032227 932036766 821350830 940889120 807619538 881033697 759418540 452375761 646130208 58561967 775342788 63771872 972338514 594486784 376050077 763744374 368664799 531488413 611138526 748440204 450968915 139607685 611437359 322635416 630291258 156007744 15636678 727819442 671835834 898138824 813128658 234138199 40729774 973521679 173038799 563840574 237844597 709599400 313680782 892055686 334050085 192779731 235020425 354845859 567503473 644740381 773658595 765464120 928038984 5897…
Output: 380321545293

Constraints:

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

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