CT64688

The Secret Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the otter slides of Sleekwater, Bishop studies rows of stretches entries. One clean number will settle the guild's oldest argument. 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 <= 1940; 0 <= a[i] <= 1000000.

Example 1:

Input: 1624 723905 817528 913740 183563 81375 381040 953004 127258 281773 985545 465995 916758 564378 969941 803563 214057 659876 934635 764409 596096 456509 698230 481501 566420 980300 745150 412154 285223 208184 439760 314089 340266 392250 860085 630036 43628 485844 999886 369280 677123 209790 156255 970352 614901 541059 729080 941939 244381 185085 253601 38265 201959 977454 284127 682993 277181 792499 101520 927069 28602 640777 773985 689920 464044 636564 923922 146913 595733 761403 963327 80340 395315 252271 373945 824557 876513 419085 580830 435794 937994 380974 283934 725815 803911 636773 958898 340094 722387 762707 934373 640794 298090 271757 197367 889882 42150 282821 585461 902864 635315 537147 188657 570542 569320 664653 907933 416025 554822 721810 116881 7179 120470 166759 74634 28593 …
Output: 778706177

Example 2:

Input: 1411 547149 360020 660529 165361 54366 620847 754333 654035 523717 920873 740483 442565 666643 789342 737060 125721 429342 691736 361811 929922 128577 653577 760139 102512 714518 590097 295534 3048 506006 954568 964158 872359 264658 906240 438883 897648 535368 862674 880392 675238 729358 262187 185800 868634 311310 871503 549744 319880 601395 560389 785881 804622 213806 576085 486980 57171 360011 721242 321414 18826 257008 781844 994541 299321 305204 517341 569417 101810 215271 270965 300605 876930 891300 160932 383154 471720 196167 629542 149011 671446 12173 350328 894433 295103 169834 313394 66812 777265 731607 163021 879590 894694 756924 885171 366929 645641 862720 490644 14098 11070 481561 381157 576684 572683 297049 218577 995213 261521 649129 599149 866227 552913 586226 485876 631630…
Output: 685740938

Example 3:

Input: 1874 565115 269831 147597 19858 359346 378517 666561 249396 240680 707470 174977 434251 439179 208946 761418 975548 584289 803415 50238 451689 842870 391955 747054 825756 132658 16158 926316 16537 585858 654882 150223 923208 147749 453230 981513 895008 708286 219183 326995 107092 725837 614633 341834 524315 741518 504517 310698 626745 74351 322620 4943 361724 198254 625355 22332 911718 135349 410164 184927 817459 675192 863884 560656 936050 524187 815566 108287 38876 551121 733831 227376 126517 421558 34955 647492 71665 989746 168357 266518 969193 41871 542963 198690 53653 804141 134060 668796 672761 804893 635867 614547 753529 245625 89030 371472 760247 719042 957935 590243 106374 45248 282596 876871 707615 685544 250799 231927 935491 96639 267562 993122 152089 865094 717824 702383 726366…
Output: 924084750

Constraints:

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

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