CT52158

The Rain Ledgers of Vineward

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the ivy courts of Vineward. Yami spreads the panels records across the table and picks up a sharp pencil. 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 <= 2807; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1842 942249697 153557965 817699778 950197456 354988197 158364170 60221674 915303695 251354740 451947784 566713952 334860241 734841844 380192728 777663363 515004399 559621669 901525018 909674881 73841664 690614675 684581463 980985851 149652377 907152948 733208739 936450458 854509814 460955798 276059367 438772109 140482910 306041566 350194897 986139209 70806905 515869021 486878323 845749151 167973347 748226353 841319525 824338167 913242141 606392633 788625937 723246330 368675544 725752821 91467722 133005100 622893290 564366232 348478879 565876058 597439007 112112361 660510221 424202556 650410011 961986627 340065801 992269781 434695060 661593160 564280445 943976121 56445255 618828406 657754579 860648162 419880862 365362293 81449405 91523648 403269152 35637338 926313191 901655820 181283371 534…
Output: 908341998159

Example 2:

Input: 2657 575129023 182894947 804070204 451605620 393445764 887960774 863934742 681983769 866349779 694305937 285140261 721497844 115859149 505398737 51978365 767861234 729547393 469215937 425119105 310399613 201026311 105890535 604969578 477851511 426593293 640264346 110669189 769344429 735189409 522694916 886904121 526123794 900922824 842093540 32224542 770781096 700318433 453694621 412467786 178762135 89029555 362173423 519911191 877750610 356268554 324984691 104491813 523346313 721981849 639588389 855634746 378696719 581616244 9844938 336952991 438209212 644877714 494863060 258477608 455256851 954237676 489581931 702149899 997684701 72548187 910716621 250892997 992174213 944431082 820902324 353631023 860132776 819569118 838990439 243356849 883218591 588722662 190316640 721082920 237075781 6…
Output: 1323555896961

Example 3:

Input: 108 963253730 563266761 245884392 70047555 851463019 956217985 402658416 716625381 41118659 621108718 291345011 328971275 17112995 32591406 253524351 952973063 79862096 179210305 82508744 52738676 457065312 940850663 803554248 480737958 229007450 177380831 518686814 429742379 940375640 99890761 169283763 33870734 797512858 232889381 80979288 266090793 801549919 458051247 140510327 236716075 899899560 550334664 282781770 196938325 73072326 615146065 72127673 764871872 533239270 33667844 675990528 86267377 771748836 698250512 713286457 690512934 860339277 103306031 779962464 351185325 176960061 294026428 110394594 668845599 806071975 39423992 300193052 140104312 836891666 81124482 426266267 344901533 400287493 147186499 793330747 449120392 375325642 674076345 347501367 356565924 733695320 13…
Output: 55064856918

Constraints:

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

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