CT60832

The ribbons at Duskwood

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The council of the frontier camp of Duskwood pays by the answer, and Pavel intends to earn it. First: the full register of ribbons. 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 <= 2472; 0 <= a[i] <= 1000000.

Example 1:

Input: 1779 766087 643159 987703 543409 483653 144369 572812 505127 897176 287530 754651 931385 915608 857685 201718 317467 961796 203180 494875 591390 894915 970793 564845 504146 826217 573729 830535 578371 149822 840619 111368 935890 321808 353538 797802 190886 556856 731255 599414 561310 802020 374105 879111 394710 982295 425517 941523 291285 89502 419599 663644 415401 92450 856269 438740 613885 404884 922114 609330 65303 32666 298794 143780 483570 879476 958622 365674 413172 526506 372505 314537 10897 259354 720118 434444 853572 371756 851526 647230 2188 533853 109453 551191 273856 989940 462709 320984 375749 622578 911679 113866 17354 778221 267434 263857 313917 233122 926522 436546 451799 985000 451098 883011 962426 145693 526775 66943 523614 63796 454039 413750 410844 714722 159846 434799 …
Output: 881909801

Example 2:

Input: 725 111719 429016 762336 791459 191128 305994 670501 522755 806896 725046 906260 367474 644188 854745 347598 56583 874694 792746 867634 699721 291607 531931 582674 40284 139842 821773 428558 821400 20096 341586 207223 530423 975406 565858 334982 961113 534610 785327 932396 236732 243266 173649 843060 960394 421401 245879 509435 228407 393490 844232 173874 338741 229338 142 260361 202982 685061 560061 461691 457534 898114 918265 405539 845500 685534 437274 946065 765924 367748 89797 274999 727351 859044 537193 607337 95256 998178 274982 466181 287809 45050 552328 742296 88584 572679 901974 332892 741641 99232 933367 710738 992377 922717 432205 255042 622437 431394 141128 663319 439478 816184 608556 81734 893514 81072 491130 392974 708567 755665 923723 335531 788648 337571 862439 936751 6906…
Output: 333206070

Example 3:

Input: 1897 987455 226895 427379 566434 761849 924250 453728 862668 909777 91652 62373 430558 916783 105499 389322 737034 191365 474806 635052 490516 696825 947151 218785 826182 990932 985348 224653 328794 72691 971056 580341 878763 10040 948661 407509 304921 304219 470151 801361 705433 2914 619582 374817 552314 769409 951731 880798 918550 821642 393205 38706 402440 576999 305446 942055 2879 565829 250507 572226 451195 397652 708769 34467 611271 83946 790551 949095 120022 257441 302446 454531 325142 884235 355542 375927 394289 982424 428783 476373 201819 774595 3919 434522 598088 141235 129231 494372 412381 571110 606443 716815 328959 871484 230536 644682 320230 265362 728450 81791 526185 766274 731828 253219 776726 642248 220996 716733 748318 431060 243866 782997 24983 6345 84970 734675 556026 1…
Output: 924846740

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The ribbons at Duskwood - MEDIUM Coding Problem | CodeTikki