CT58687

Quartermaster's Rain Ledgers Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the acacia flats of Thornveld close for winter, Quartermaster must finish the stretches 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 <= 1433; 0 <= a[i] <= 1000000000.

Example 1:

Input: 953 63149861 156985696 146531499 585483829 772881927 246220805 157337352 476972259 123743917 307608035 971943375 536000116 834551307 296499448 643359858 474940375 152580597 379482988 657649971 651884457 324960272 442629489 505786876 493455186 251147933 734742745 340950597 597448244 554060716 845044909 542625313 726263139 869948374 84328929 330376777 444016891 450709452 301061180 269667605 524895890 179649153 223918366 49606538 569365972 431533330 916032724 910904696 980383471 798732012 237376000 649592635 925763810 504325407 367608706 139611381 481156659 298056672 971660227 481155818 733703404 39415728 711256194 315886221 445997145 348125220 751023688 333940388 63877181 969803518 517652666 394666507 148444176 624031058 897065514 471023929 337724627 96645148 910343466 593947488 748885672 92…
Output: 455061916311

Example 2:

Input: 1308 747154831 406842382 57644361 963750788 952200263 253740510 730393669 196865476 392592600 358672738 723348074 617825444 117789740 342177903 729141542 983228337 454535746 472817255 711996814 987838880 338801945 353771281 441524165 500869078 205254905 89827222 185975099 214554931 628693337 73824943 448323320 667820788 777233828 676453970 812574229 176356842 971378248 930578311 758698225 710356635 698425687 814705740 422301840 153373944 950834605 475822244 158581959 278711541 654992678 197813441 791080539 688995854 495475283 751810023 396012784 837656868 44790391 940925898 42616255 898994999 23120960 859937536 556395336 5949012 704966334 960744780 119685254 150784428 103581375 566616195 961289153 699085102 127835867 350637024 822213316 494900175 251657859 229628337 181062580 978721241 252…
Output: 630848254668

Example 3:

Input: 924 108809149 375052831 796788989 731074184 289060458 133651111 252000733 664995882 819307287 850380876 971382505 693633876 269385062 587415898 833989751 177634829 874067529 485694589 994526901 29752384 288299518 270740705 161236300 584662631 230865416 253391546 654986041 403028888 410760224 213159043 260810671 223126986 256650923 470433548 330840918 649716128 292510179 276993192 861691611 727386626 640901472 537367110 870727867 261664271 3377217 796989824 529270461 872276606 288388225 374769899 749110949 683465902 589232278 481489626 512717331 334664584 139960030 650546144 631857991 601282180 927445092 917177454 66199382 47435858 916791792 973781044 748500977 855813851 358628642 36992893 225931921 353405540 5037963 975301067 144961494 544496818 786601062 766898829 847349614 214946675 3279…
Output: 462718150110

Constraints:

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

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