CT46522

Urmila and the Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Urmila the paymaster watches over the glass towers of Prismhaven's stores of stretches. A careful computation stands between order and chaos. 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 <= 1559; 0 <= a[i] <= 1000000000.

Example 1:

Input: 628 9597937 481677009 126060374 537392836 758973460 186307152 912559446 668701189 227219544 348488455 420508097 901144228 374336893 57994757 893379655 975561336 155937377 788492359 554895526 688076676 338724609 658090714 772224439 413518427 155990086 851735262 569619602 439659022 365289402 297229188 187868987 537072829 748923091 380581002 486858926 965012769 42095490 74699091 257830294 372537877 524267557 845651370 7737071 526001623 846193784 999337616 346967631 153251671 278907173 569738969 323346949 390240749 522762439 268792590 985737561 454703222 822299735 906144315 462016736 636520593 172225290 928718358 815954181 221248149 81979967 816367369 886157321 571569201 970606531 444199843 881531114 811604186 74694192 141260731 993600852 886226066 906899487 981953757 449649494 520537357 16333…
Output: 305272091445

Example 2:

Input: 1411 75153504 444948533 77244375 698615423 230291238 494554656 811551979 85227548 926000130 181926693 114846837 227291922 162713920 571992715 311667057 753106185 367075339 842320657 877260044 842120801 476361621 271037324 955426388 216045448 295933791 934386492 528606712 575548441 182778773 130143690 192906204 331602685 52399815 682374256 342428384 421312860 127993608 218141669 758580886 905122516 863540993 874400607 828962782 315467810 480933646 917112603 30156724 244574034 389143406 875474635 965678359 635261901 252601281 993549863 247428985 688913912 725217281 27390061 264105171 60343119 465099484 903976452 771362668 426433899 978290289 405243060 322459567 33466417 579952912 439524741 907999591 852514459 904647431 713549349 799412277 530847420 203574678 421564087 775493158 417651963 555…
Output: 687374978160

Example 3:

Input: 572 796847783 494726640 674761806 895020968 370410625 74223236 383948851 669312675 505222406 625721937 736733116 124065045 808684379 193122681 499311213 981637162 61887264 280832979 599395790 275926060 44284858 944251839 449549689 246682575 77104767 81203171 316778547 337299654 218884864 440167597 83183489 410311205 710545125 18955494 427435238 727143945 42770777 106670742 954505235 780035996 381471219 892244210 206871968 452857951 161429377 239470405 169980150 771380402 257416421 104056997 51238021 956684257 487699852 243228403 863952479 59399067 581946054 449736867 856217342 486016947 716532303 101206770 458157444 144377957 587661075 183213728 938330148 414501433 497834807 311121633 435299837 42217844 604872544 670526554 197643247 327690921 249720856 59540810 172362489 813189791 41886669…
Output: 274353814830

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Urmila and the Rain Ledgers - MEDIUM Coding Problem | CodeTikki