CT43232

Lara's stretches Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lara runs the mint at the silver mines of Lodebarrow. Today the books show a list of stretches, and the numbers must be worked out before sundown. 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 <= 2261; 0 <= a[i] <= 1000000.

Example 1:

Input: 2116 368013 272639 417109 291219 744498 606420 579566 493838 991554 938067 833699 965672 577546 197593 836041 954790 614576 176035 477258 630268 420556 832615 520959 324590 863709 41225 375482 751701 852654 54586 784583 63252 220444 208762 663570 651835 469622 125599 462907 264524 580407 985828 740864 358619 555620 698626 421195 101411 958554 636665 848137 20481 377135 585180 582209 16893 112241 514313 11230 473957 199842 367214 338861 792896 494192 338410 953578 705655 492892 668321 5282 878336 739172 958194 676866 768915 422971 549074 831380 623167 18506 223150 793090 431478 967757 182462 43062 476172 930613 122996 931701 97325 260768 768826 450828 99981 463693 801746 201404 477840 77462 620329 966955 357276 232700 436435 787942 14725 465415 762152 605357 519115 933496 976248 224299 2110…
Output: 1040065716

Example 2:

Input: 478 43194 113849 599689 398149 182339 270673 353799 587889 431793 713537 565726 263956 122025 969162 207485 343804 391494 598935 695255 380372 279112 339131 819642 171739 868813 244703 8487 402140 757613 609854 798706 246887 412991 147435 491623 70224 723385 459767 860528 455904 877399 966567 425228 686925 861451 130667 3691 568972 63747 296584 507007 649691 551622 555257 134871 311812 397232 469559 862640 289674 392953 359528 968383 686131 2640 636271 732755 689768 994233 253603 861142 85731 274756 871994 684554 913643 628110 419850 730892 419138 406440 778142 981426 431197 928766 573261 638059 62024 997061 906344 100843 903494 670907 213941 31225 511323 946276 22768 581009 995968 83248 465437 330920 484813 467553 226266 849178 819438 456746 183659 269640 307768 772884 575049 512346 58361…
Output: 224872367

Example 3:

Input: 2067 392384 553164 490234 552443 997237 584408 719182 781877 81448 68459 44266 244430 77108 834244 179095 712356 561658 352059 830938 461450 786345 383669 310906 794417 549604 262209 505494 386762 960251 127404 768544 312142 469785 57914 440143 450702 800258 779128 997917 787264 360837 389805 487836 859271 67514 994328 25328 448538 125255 737338 505280 199953 366777 478716 124136 6903 916704 574647 28581 53144 918339 375840 642104 635369 849394 603498 772698 478397 121272 337622 197821 182464 23314 241244 92312 296297 177564 732719 345769 358712 681708 142256 417708 241870 193611 389643 587409 215646 435227 609804 778571 866948 28633 5086 372879 759167 322931 808686 775108 368972 563606 933983 261109 369424 471447 875248 203439 183645 153584 530505 203088 578236 68060 357793 521799 478142 …
Output: 1030207687

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lara's stretches Reckoning - MEDIUM Coding Problem | CodeTikki