CT37075

Jessa Counts the ribbons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the sulphur springs of Brimstone, Jessa the customs officer keeps careful count of the ribbons. Prove the quality of the harvest, every figure matters. 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 <= 2814; 0 <= a[i] <= 1000000.

Example 1:

Input: 1432 686761 200519 443965 44138 820176 884418 91495 203078 514800 543871 584145 298494 995582 296123 306736 409208 987292 995815 213912 456567 931196 425233 654826 225495 566875 678808 162587 769639 679886 304178 598467 82566 346336 393587 22621 251087 119084 142885 928191 331829 71697 833633 674544 409589 66313 991133 189988 865955 329795 474179 293142 317344 362775 526914 450297 582382 141990 738172 230800 860969 907430 279876 212767 189735 426882 914385 141103 641420 860845 185011 468160 910695 323856 602793 247037 21903 601927 894192 824928 291884 475690 576212 557302 488278 951500 441986 631025 663814 215698 656264 70198 432230 723536 45194 550984 830305 406946 677072 314793 540790 842312 916579 500546 607721 300388 325717 567925 738848 320071 385960 528759 334674 819498 690245 756486…
Output: 696837923

Example 2:

Input: 811 595433 819562 52818 198123 979704 550416 911644 567878 880529 691433 214756 89691 454473 856294 375248 520464 801904 891204 593308 608948 773077 756786 426530 166704 767819 855184 692331 526377 167463 597059 699406 148436 232356 431153 941536 765660 323149 316861 275471 548727 424574 848016 103754 913917 889528 981024 73801 334907 689422 337028 279780 325916 50197 635763 544676 147815 293312 651802 224444 431208 438864 117419 912145 573358 598920 557682 749742 169795 497291 422156 929296 42081 95313 984992 874338 872209 851791 481338 457178 600355 31167 439071 559337 732805 73600 789836 23886 487941 572040 372882 333435 780283 809020 961682 138177 743042 568962 75051 34389 720212 792923 228776 115897 671062 369316 865484 79534 569742 214121 82061 480204 492225 91769 439746 995146 74885…
Output: 381800568

Example 3:

Input: 236 874030 400546 425750 557570 485649 149139 540296 526453 690401 12837 622708 146542 50813 109809 873137 439150 482408 387799 586292 633715 946899 529338 449109 215055 408275 320454 733342 371282 744009 671341 566650 330852 50565 995058 399589 363542 819175 65194 404086 865516 495558 625085 752370 728111 955379 784308 751245 33806 167567 534321 480500 780352 418686 591294 239290 408985 610591 61349 957477 659945 881012 538604 834846 580490 325913 69581 615899 138549 691113 997835 690465 731777 153187 722651 871997 713591 284330 181196 291466 788871 777197 421468 794547 915906 921599 29728 539177 595253 379600 560661 702757 598639 308566 421608 7750 313310 806576 415450 248883 757612 884238 379733 719625 198331 178638 125663 944336 253937 371981 703613 785050 294473 410231 323797 407540 3…
Output: 107528367

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.