CT64132

The Wild Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the gristmill of Rye Hollow opens only for a perfect tally of segments. Uday 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 <= 2622; 0 <= a[i] <= 1000000.

Example 1:

Input: 2573 423942 360669 661204 121175 342811 638105 489519 397575 436641 413897 544946 113252 55896 858833 209572 130230 926409 346861 616634 244647 844664 427717 487622 205322 173320 864587 609296 229048 886441 54173 495547 161056 171979 58945 600483 775381 517464 951739 124327 850816 713957 761935 140291 750541 140697 929820 800692 508935 443271 587748 61396 820686 196094 249262 949833 832311 763335 452466 539294 175353 175928 673092 458233 472727 95662 237871 87330 539683 811845 729937 45423 67470 306054 736540 903459 751946 493746 203953 387392 352725 571206 290206 180920 194640 585067 134207 611570 592821 376780 731702 452882 850310 177949 16050 20037 961917 15288 325003 537159 108654 86838 876965 115504 156670 237952 53091 208344 689234 478930 692945 687305 119782 339783 477257 515454 477…
Output: 1270214644

Example 2:

Input: 454 418680 336404 722901 744338 7881 436676 471017 139644 298253 167816 854922 345236 280196 907000 124079 952643 870934 448122 443075 581248 919917 242545 390748 371410 751867 839627 901120 400071 761154 974389 54354 682511 740207 338147 329364 279918 364650 12460 497127 944806 579273 264320 422780 825803 128860 987747 123121 234089 202115 35249 493347 851576 875571 308280 652965 269812 169864 579646 865546 204105 756848 658125 485883 459088 912443 411549 964253 689503 239382 632476 644509 334421 445287 667825 823067 309417 265098 631031 883535 333771 579236 842300 305653 752826 770215 298442 405796 881047 53156 650966 536786 124260 1550 328977 202400 233811 239821 677707 671405 302468 569278 23717 192958 481265 560204 838627 753606 204670 222533 35536 284962 467222 153082 505331 820157 2…
Output: 217614169

Example 3:

Input: 237 860987 6853 652118 824929 937009 387268 359126 377900 323224 509243 513791 382095 852847 655896 198791 384827 874024 32316 400161 683151 47268 142581 128218 764858 170464 389509 941854 520516 130985 780856 302907 489871 695726 79736 803405 949255 969725 100781 891246 210521 757467 299343 347894 791069 418304 852169 497529 17259 883935 92655 115997 638135 775046 650631 810617 978279 820812 857020 908534 626311 224682 441851 818290 33147 78163 883934 742281 943066 994953 314220 507248 422305 721389 958004 720103 313144 647863 219350 834318 555071 710459 598233 615108 71598 686144 813474 831987 508976 853560 540550 362471 985768 138010 315947 250923 822010 709389 278777 289738 825032 200692 376221 410677 15759 916890 721838 169499 665712 982179 625641 949097 945432 542850 572918 360042 12…
Output: 102900549

Constraints:

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

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