CT64563

The Silverfin Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the herring shoals of Silverfin, Cartwright records each ribbons in a worn leather ledger. The guild wants answers, not guesses. 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 <= 1750; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1145 205874038 460187276 999435879 19489762 567172510 1295513 595854926 214839736 613607388 769291313 500423163 560297512 251694141 536010566 814730911 306734314 671133514 769444716 398336840 441430953 199581507 468866535 48088726 173126540 910297151 695673134 467757081 739614540 597020484 477321161 198073761 152310324 508649892 459112422 569761422 488698010 353286916 223171637 942675456 941316707 146752444 960785920 836892271 80698539 930624467 502442350 841048926 63889150 914507223 152013080 251979977 65468907 300006663 799436644 45384770 847219487 963370425 732497553 825182792 536146351 820752332 799336772 946936002 750793563 852129490 603452785 980623196 92336396 814807131 768475598 135312492 930722194 246943513 508335457 665523591 408846862 528742954 996695535 694538958 708544147 9251…
Output: 562013511865

Example 2:

Input: 1357 838030426 897923484 34237773 263522954 583520685 598099058 351469314 799146793 140744075 654082307 762027208 981431556 515788551 906076234 765049458 924346443 821442718 465582638 942807459 172592325 225450752 468604539 105881425 793843611 222553846 9653482 457076408 938585191 934699764 121452595 663525434 212041523 345520956 141687710 396186209 943949313 983535188 769112103 35356842 930167936 388723387 34642423 847199212 304622730 855864219 401832664 349477791 891127783 631283168 454050469 569819526 778462506 391671024 91653761 16029672 202583590 61813769 485710380 696915006 250857086 252023013 337318326 115077574 747435133 878294011 136377426 448294702 173270819 288101411 49111202 333846427 292788978 262655796 216866288 23525761 309544408 696192998 775226222 555476301 704771759 65539…
Output: 659266009150

Example 3:

Input: 176 285074268 309339148 598388414 967087378 806997592 202142079 825390053 277198950 539419522 645585335 615487028 455237295 818361698 483610751 814148970 260519821 384406196 322304275 743225120 715328018 839551297 169227161 133093459 616118043 518552545 805094073 462630154 190710596 56744548 855105271 187502373 623410843 205316860 513608893 180222519 29423926 482179271 563512947 940331268 786310893 552940773 943279389 714545654 914037030 375743145 936918377 730670884 473579115 304660858 269455737 393258260 616372057 438515148 507965786 830829673 656182866 769981810 138471349 906410509 111079590 212843949 725608243 638961657 367146020 619231103 313090084 147874624 928224643 910549623 388982886 963320277 241412695 819313052 260991334 775223104 66548527 695817062 639041079 72550058 154663996 …
Output: 77111972633

Constraints:

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

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