CT38573

The Rain Ledgers Beneath Rushing Falls

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Botanist found an old ledger of windows in the chandlery attic at the salmon ladder of Rushing Falls. The margin notes pose a precise question. 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 <= 3513; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1079 137243910 644873028 466477793 978897506 90160821 340303704 899427628 507296471 645908649 879013019 792798647 725187507 689086765 433596024 837021115 43195547 525527517 69082042 625064381 634376002 268438153 571227193 830299171 677058293 559153967 31792938 231324596 593064507 627967896 282275766 808039330 16112406 664428253 296179694 771532051 453121256 264426895 359858032 929591096 833545726 474675961 647581388 391391152 864200646 38615958 516246513 894098980 397285192 340118852 692445464 586937406 981217411 301774087 895536827 69970544 114345609 331987576 825762331 342792306 81008711 557688669 10633815 804507713 881641992 382165790 319284449 71671409 186270596 690336581 204597619 137107606 494613620 614610519 332763418 79440896 956070565 598950860 910930542 703716387 163441503 951415…
Output: 530690581525

Example 2:

Input: 2813 930055253 405075156 821684719 392338569 407597621 600081295 316329946 20657658 190116871 453672302 569219863 805479088 62878850 899540272 449832826 642234159 118566165 916092908 273299121 755526685 252830808 352890334 929881626 809605825 424483931 885560934 547023482 245094300 583807331 524703968 622762697 228476192 456157325 258779019 841305025 898887702 542559882 254061828 537621700 197040440 430557751 944669747 492492316 607712583 883318137 824182377 333682484 105769600 359221533 301498316 154797959 869944617 580369466 736766387 95119441 761261793 944915279 471858194 905071182 800628083 952875969 970740254 408754857 602346061 335912112 276864857 882333881 563785837 954638477 850221069 65498618 377020984 801850320 840236330 691728501 808160805 559477299 578057246 966419570 411520401…
Output: 1404226307231

Example 3:

Input: 230 564757041 731246275 407446576 884498934 390735919 195749559 331591529 415605007 151662125 886305310 555304697 61917543 161443548 274438456 976061074 515380958 293062172 250826194 746627695 71277185 692088752 410431520 941343936 328002191 911057183 493093282 229606281 508364879 43145551 63409769 209779271 487050175 903076514 750579745 141210425 478663714 956897896 757285180 661286231 909583097 228932854 19553371 503810598 273288935 514570677 635429189 97992996 994952660 49924673 15941155 973149623 364735030 876962147 4582801 624483913 447151840 315590571 549953144 625642314 958557232 982970596 322829022 220431812 794261931 795277408 522069252 788332012 616773314 794870805 943216590 635309337 993143577 447873272 111003303 874047890 331406862 888674116 491126367 205398719 898636167 495900…
Output: 103960201129

Constraints:

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

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