CT61067

The scrolls at Grapehollow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Viktor inherited the observatory at the terraced vines of Grapehollow along with its curious bookkeeping system for scrolls. Time to make sense of it. 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 <= 1935; 0 <= a[i] <= 1000000.

Example 1:

Input: 276 183810 348941 907858 834323 152688 204474 159954 425553 303432 962197 533726 726457 763318 613095 370232 915183 298606 667266 296296 820850 785237 16386 104635 466067 245670 680727 293947 484768 4119 664370 181139 690881 73031 196606 33899 270765 888782 525076 97045 309540 186905 741269 865047 985347 215470 271434 164008 85649 130115 311072 63114 197031 449067 949287 873417 981846 50896 794507 908969 640612 284736 851383 218034 585608 24266 122400 683783 835129 367095 737585 48738 391565 265888 879439 117086 900662 530254 50877 210452 737459 903990 875952 961972 308305 305943 657371 715928 512765 596900 546828 701202 93644 821696 825756 538137 314181 834079 511903 623517 548682 42858 454098 669135 889153 10229 214579 918143 800387 982632 749924 233007 547626 668690 179742 591620 166998…
Output: 125001730

Example 2:

Input: 1151 24742 42895 570881 398442 117535 592003 333329 142788 519274 653961 609407 987465 91972 491386 642196 283509 510645 990824 554814 571690 708238 277069 442605 146695 830132 80666 150307 310003 450535 910847 500642 523861 992850 73384 813132 538937 793490 977401 588743 266739 865368 89037 536652 114814 157471 826212 986189 626384 723642 479276 430443 450711 240292 896653 406064 657821 598457 852435 284615 370205 532797 458356 384717 382797 181786 849113 477295 602362 327470 72539 223910 900842 114793 856623 227994 528079 559776 547551 890782 606246 994116 508388 284997 382997 434620 608515 653957 953121 908857 299165 72416 706137 440426 402610 433756 877288 446246 304310 109072 603440 249442 114926 912478 129790 840691 616783 643906 370580 395636 995844 149101 777164 423398 837115 33182…
Output: 569460180

Example 3:

Input: 467 484993 479809 442272 520080 730136 307028 141762 821666 461944 961391 195699 565739 135668 427627 476271 901745 898239 867869 883801 524308 371912 299041 587862 43476 668868 547030 378302 838971 10941 954670 285977 385305 469038 661003 550567 672680 53752 401229 476923 654322 22152 447652 162402 322138 294250 211377 995158 398975 8663 935741 114024 729865 445491 90714 778760 990890 989876 581476 841968 211264 910514 667557 102446 563281 649596 912987 285879 299602 239595 209266 201497 644007 723478 1275 437106 700066 950431 792945 315677 791529 916069 604806 684417 507410 90898 82544 839886 627028 234108 261076 290464 989401 478563 245014 183007 884383 69663 250258 829749 949617 639974 212615 697194 653080 582642 972969 171149 582949 689210 466036 691934 345816 621420 357297 38078 4426…
Output: 222188696

Constraints:

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

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