CT46195

Petr's Caramel ribbons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the coral atoll of Pearldeep, Petr 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 <= 1612; 0 <= a[i] <= 1000000.

Example 1:

Input: 1142 634192 206158 961464 920196 409702 369459 174643 226897 822506 667613 930475 649736 122364 132888 984483 696163 752652 59045 637373 446361 999112 881854 386523 159620 404702 565875 553980 545456 984735 688755 217301 709436 77786 83729 672600 394734 1422 480183 100732 466380 42508 201137 502616 898043 421724 168 437806 249600 338388 959545 743307 356880 77617 606826 36983 587685 675653 309683 539635 351488 831557 590564 823371 801460 810863 980010 492420 113399 277084 11958 83676 230675 335995 439099 422866 863604 665695 434257 934349 258072 358711 324745 572401 997692 765006 365500 839504 742016 106674 149227 936329 787107 942654 203234 176221 731505 776902 963763 899279 700664 161272 403742 205520 242832 512882 198214 662274 810958 986663 744944 892429 161832 101705 376774 970257 894…
Output: 554545067

Example 2:

Input: 88 568986 363771 591589 443487 455646 268419 737560 306354 29772 780353 903677 530280 111273 386226 387083 83698 22263 315329 672764 429520 359202 249093 431036 993457 737540 90967 182104 600828 366491 120553 306064 767621 404740 124891 394164 8676 708113 705230 868460 29441 30951 586701 582979 143548 324173 46529 986559 446356 293386 195215 756429 201831 535253 717528 85509 427713 710365 725725 155600 434376 671174 871694 836804 99542 400965 813731 651639 706630 91129 451896 600072 670594 219548 735186 44413 958864 940001 424797 291181 376505 564450 413149 493036 963708 509979 100169 298034 706493
Output: 40283814

Example 3:

Input: 993 702694 647611 585019 466310 131828 703388 529742 716620 688707 72199 505020 843127 773524 940185 108424 946315 296916 356003 828844 445198 6105 115685 74799 862473 804015 198503 84962 594494 800810 173477 411288 553708 673547 774052 817496 849760 63036 10619 969679 205089 639753 619369 759894 575238 373824 690947 576543 583921 978511 628639 833327 760394 770722 83381 389931 616609 737308 211546 931739 27769 303450 511550 592889 246936 625493 657817 766164 892237 947277 55458 963074 109898 130249 254491 980852 856229 562768 376485 718767 92952 809107 948252 120339 576482 625499 247066 409601 55108 710057 255968 781408 760321 673256 226637 79211 798671 807754 178434 530779 108430 292719 595194 537798 223834 415441 118038 330352 165540 983235 661737 809716 464931 813150 312798 848515 7301…
Output: 482191612

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Petr's Caramel ribbons - MEDIUM Coding Problem | CodeTikki