CT40373

The Violet Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the port of Emberfall, Weaver the auditor keeps careful count of the windows. Tally the donation drive, every figure matters. 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 <= 1972; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1544 107680374 172650094 543138761 225375885 863741978 673867937 873797644 739355944 67518768 184191208 442493430 430885725 172251297 425224137 290762444 715670116 715721387 624845051 319671806 620960082 636743489 458365113 502105111 590693925 789624983 492875457 142397908 58736891 552677037 402361604 687591115 619890368 51515828 151526459 599322190 59433956 861043467 348882012 573793333 596113093 62588567 315304672 129532193 199878637 155441597 861804671 152862069 426000014 799493000 573311138 73356053 737393213 692277713 309884035 358320677 937641300 477826106 929563900 509768772 527863658 204019445 458465388 545909560 551516684 158978342 198056174 169093137 639017070 693294524 930855619 989577667 130011627 20598913 113526964 226190312 804752536 498781807 560218489 387450340 526092621 72…
Output: 753461516452

Example 2:

Input: 913 788976577 712221265 379800321 222655754 499282053 688702790 327890683 481099866 178419541 253354155 477678945 849298925 720306531 639049380 865706376 352070646 671807261 890970100 421236682 574840483 247958449 897346847 600555314 609850087 157171448 46675814 211251152 434575675 319047816 621344044 354342403 423479189 702903998 970637220 734661562 609629950 969146753 592331580 627917119 807788395 941468463 981883688 758997345 834443339 677003667 643175210 557821446 686655801 916247562 108774932 568260096 946186939 489593616 788362878 735172886 617419578 46098341 734034273 399232703 93091231 848441912 708986080 8391182 464147963 747823021 405851769 663555207 212341226 233366361 659777208 59219953 48001103 207869891 319944611 35730159 129466307 202842538 177807676 332757473 371478799 2375…
Output: 439706463520

Example 3:

Input: 695 137791017 571529053 89908069 781248835 752180241 540048179 833767066 961002279 866095598 234182749 80362298 163529182 697679862 699633012 449262942 740810988 822210628 630936948 556933030 696579320 61488734 937483960 969723965 835944853 346907517 9477696 126364821 407969565 390331314 81968805 851420344 367805680 647722034 714421499 4755199 172961835 965366039 271455205 515339314 68944759 884589851 444693385 403335728 367998983 282449053 103268156 649026963 473763591 459759650 881428963 631544572 370331226 482481276 837711239 612500746 230443629 908366649 325038029 851187041 534217491 635845654 895113122 25598827 207684577 320308975 246452783 474099990 483253530 855259722 918073057 215267465 688950009 611359964 901149458 230498598 760052304 607063107 881491133 245827577 636393143 630923…
Output: 333899036072

Constraints:

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

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