CT62943

The Frosted Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Tanner the log keeper watches over the boar woods of Tuskmore's stores of panels. 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 <= 2203; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1174 925500313 248065393 812913632 360077434 627320757 933995588 779615554 795417704 763624749 231287832 673231817 784365801 619971763 201529339 734333770 536212948 577760441 263301360 967316423 464042050 71487665 464693769 388840095 16704988 892612280 305171942 140756168 941346289 80111035 194038569 279678570 56551149 987295029 215097390 563131045 209293477 888529000 653674824 607472406 52489992 98250578 459428360 6695605 398662336 277797064 273086333 354507622 112723098 10343613 511629882 587293131 504003186 197741690 872800990 127429143 488754301 470590298 554015345 894042237 482587449 661142579 89455810 646829582 503243116 261241506 759726036 808853244 758515306 889119963 328340722 693080481 322792954 625346814 378597757 7130266 181406681 786317588 137097896 712512607 581167285 2655199…
Output: 575589470425

Example 2:

Input: 936 16545906 959856245 9282652 686853463 20706792 469247211 819434326 209314616 721199414 316203960 418286565 887955299 899351125 181209630 623012205 26620517 411827554 700596819 127166312 566963032 637783385 74544237 316582064 773333564 889124515 98872453 769903790 43594598 915291054 355916066 813678824 60917409 23699659 615619155 236890020 965094610 534173813 285017484 53279385 715749531 337426449 298206264 665802442 724328101 603475560 248477525 205084269 255565134 108016890 759231938 549041717 123590178 388303916 434901385 521852919 232129918 198274703 555519033 451600769 202917520 919225531 986638692 953700904 732477983 636312361 17839739 941566856 565497572 306532887 630969445 482696209 850188391 885629630 781805116 371260743 92667407 462666832 827037049 992870305 812196502 233397406…
Output: 458748660660

Example 3:

Input: 1458 332276111 677345077 17787045 117106684 710896668 218668459 127570837 840794316 756392373 495754666 628973515 918598652 536637850 101549466 843399898 948916724 821237890 610783471 35137766 828785485 363252459 308938513 32205471 151217521 980357825 333381577 317292171 913928154 205796864 39715315 903447511 993783909 457907311 783610892 526822212 103802173 753169851 101669227 151057569 318996509 984157600 376242918 523532907 478753646 477948284 542738332 136123467 153005922 521944109 628440249 89430208 511956925 596343937 533121238 469652694 170912509 515248521 185862395 47780197 596055598 432223027 682852434 89317656 955328811 674502175 331749915 731378650 3290639 656012595 502683270 609615542 953899835 509206280 367453488 245661203 583263039 918800598 302282629 695054799 408464379 2019…
Output: 716019095036

Constraints:

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

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