CT63590

Varun's Umber segments

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the northern keep of Frostgate; Varun weighs the day's segments manifests and starts the calculations. 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 <= 2689; 0 <= a[i] <= 1000000.

Example 1:

Input: 681 3018 115218 645771 386214 606615 722554 868827 982337 244166 116566 850661 730192 16209 492135 137918 673865 5547 660067 531490 825940 537149 697349 106163 313918 934940 607901 81332 21894 885272 436506 269726 296401 227423 362002 595679 805416 41314 383466 79654 64929 275730 702003 828426 286192 9246 122566 150757 559755 644865 429303 645102 227566 894039 142202 515984 901675 730012 756030 871852 978526 794800 10264 325411 870265 13051 922321 129542 993683 648757 278160 373333 375435 914615 633657 83344 157694 158624 335219 760226 833473 70314 16043 98221 552306 943320 352681 803846 90157 37729 499540 498162 388819 795332 446970 185835 463725 510884 707431 484246 674532 471766 690023 106334 120425 158834 902755 249183 974009 47745 170399 660299 760280 672788 204086 620912 191611 56943…
Output: 330750971

Example 2:

Input: 1613 284484 676367 174212 810617 936804 136535 499717 175365 551730 861425 922350 371808 225720 368856 72057 396410 511098 958477 53161 282533 559514 178552 213607 352039 230832 161022 192514 410845 231770 557006 665771 234839 864493 948887 568753 742927 231881 166138 436 970341 409618 799637 627812 999674 198867 281923 31577 623285 654382 188049 429498 888825 69481 208452 688306 177296 127518 279869 998515 482378 492283 501883 455868 808681 274839 435236 853869 126019 195901 226397 966758 595636 484396 684472 328320 705532 376621 80117 348028 45213 895775 692098 610761 203849 272349 91926 83291 815888 473973 233943 619664 113876 552224 767741 486801 935475 591677 364082 556860 610872 92916 638809 379996 464420 985586 900204 188258 597860 604106 806982 103966 823007 887578 430435 856575 13…
Output: 796280533

Example 3:

Input: 31 256821 561084 809066 210894 173506 367558 717355 443600 45354 483938 809480 424737 335958 953019 365762 275985 100366 562181 538619 425939 483609 125316 58613 125198 75518 71594 433743 340332 439304 159377 9025
Output: 6926436

Constraints:

1 <= n <= 2689; 0 <= a[i] <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Varun's Umber segments - MEDIUM Coding Problem | CodeTikki