CT37718

Last stretches of Farhan

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the shale slopes of Greystone opens only for a perfect tally of stretches. Farhan means to find out. 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 <= 1334; 0 <= a[i] <= 1000000.

Example 1:

Input: 276 771556 86721 561868 569916 467979 544746 712564 947651 656625 292945 227218 886460 466885 243744 672046 773677 224592 494162 702473 138779 841308 324652 398259 599299 21722 29113 140783 237136 62335 947226 861892 985034 53986 469725 59191 533746 768653 541293 786683 313485 33918 220696 690700 566904 91985 347894 540580 137775 117835 933336 450219 758812 453843 412033 74048 956686 861621 242276 606109 585447 993443 34607 294962 837160 967726 544232 295097 878693 798520 466159 11976 642965 753546 571745 962844 329502 872532 280022 324013 385788 846612 269298 916807 226155 992858 741975 117335 261565 931509 412407 27635 300933 325262 478459 289303 319045 402299 95821 287619 314313 998904 289897 261528 954384 622009 325054 452724 468451 303415 403825 64755 287900 123878 262777 865956 35401…
Output: 137053333

Example 2:

Input: 70 728572 595140 205005 655113 448593 610990 908435 444404 689934 122248 890310 816494 545857 138074 79455 765024 342863 666539 804822 215053 176133 591528 794166 615266 224362 451159 74525 153635 959866 982316 145238 213689 158857 959159 169482 605604 341537 220433 125451 672400 112088 464498 635526 556321 262546 824871 229834 138177 793697 711205 873364 355522 971237 924172 997026 700228 149036 544126 760628 313151 906392 213334 57842 104156 845024 898517 975343 500433 115742 750599
Output: 28835341

Example 3:

Input: 1025 880784 133768 834697 561940 424545 875905 517714 619023 142855 857086 569226 286921 371665 581312 160927 282479 644312 469626 946961 169313 360886 40746 339401 192626 958571 536188 895397 952499 344153 666105 697762 871934 333383 499721 231946 118027 858429 307224 716109 709625 541055 652553 338064 676441 218714 819738 641222 960634 114021 201665 574447 466463 583235 762625 307304 373708 171587 268688 61518 799612 608613 955094 523952 11638 599515 93986 36881 920326 620183 869024 365739 921768 636565 863133 244952 568776 490267 943048 309994 747779 137040 338649 208248 574786 513895 832958 111835 696035 368490 521057 741687 518312 717810 462592 371317 104704 601963 466905 181720 531006 360407 603189 84824 530699 691193 687049 461755 385803 337567 757355 306861 862033 28911 936636 1821…
Output: 487461523

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last stretches of Farhan - MEDIUM Coding Problem | CodeTikki