CT39536

The Rain Ledgers of Stillwater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the crane marshes of Stillwater close for winter, Lakshya must finish the panels ledger - one figure at a time. 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 <= 2140; 0 <= a[i] <= 1000000000.

Example 1:

Input: 370 228482121 426815477 220080492 540575530 965938527 708039615 719231949 158102753 300337461 638895335 839039090 737975523 946348485 811608540 414081997 980501395 958221863 280949525 48681240 10954696 812745379 345473039 28100374 509902351 769162341 740930271 918984176 365501808 421706590 84981446 909203732 67082855 749593401 948741585 767325387 37101916 416478936 425670946 217132054 692241379 876751273 659048706 247033803 370596569 863728879 761529174 697685359 625364582 606578251 235876989 49603908 528381375 355438298 22944327 735037609 243692339 456343455 894857557 582773833 698935864 20007558 379604155 772641529 681914624 27839700 58661616 481664453 426405017 284033969 223632236 497481931 440021215 878729784 743368786 159622744 370973374 429833769 988994627 378945444 507105307 1934535…
Output: 167091602036

Example 2:

Input: 65 162874141 942976952 148378930 464912328 535939882 981272984 141555365 441221888 183588400 511767891 207262067 313776224 531624345 196751920 108541294 463563654 445079473 671023530 570095642 333907712 568126391 523288810 834408541 468395869 212080507 456413654 833338652 735372781 780453591 295404207 30399388 883204758 307468058 975193 187139205 505654741 340139219 934502778 723739904 410178189 424796930 556642135 100285544 268918587 441226644 771618783 53243155 150331368 765935854 889994060 559638193 652005141 651011158 281181904 202156749 627099402 645145573 338680389 635046535 247322837 826915181 178159107 163043099 107263178 595641340
Output: 27458602996

Example 3:

Input: 890 290479463 313686348 18111280 944511352 776838068 621510030 498027401 551463880 645892040 574438585 498595774 111922724 700418739 699426589 937650801 451654645 175755960 611485686 995599201 465780878 857628298 290742798 970562384 129604342 131727048 869387911 808234577 703431463 49865600 432626402 205051807 541709405 529181205 419157597 637595553 315534473 395188477 844968226 930890850 600880487 722991482 46686328 383275054 46533185 253305270 294958231 525490573 611324520 578057883 939753528 633609620 755062053 171105959 193342329 998223740 228588302 308869927 455292814 360963173 221633450 205595032 348943324 30013246 679029320 352063097 109170853 312526343 895012867 826354287 963518328 564852669 782494096 940858890 153731396 462412593 14480448 859911436 512507759 201197214 507093108 90…
Output: 428164173500

Constraints:

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

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