CT57185

The Prismatic Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the crane marshes of Stillwater opens only for a perfect tally of windows. Varun 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 <= 2301; 0 <= a[i] <= 1000.

Example 1:

Input: 1459 479 825 213 143 969 124 965 223 55 647 334 410 392 516 532 262 915 46 848 115 13 739 933 981 979 545 140 503 157 239 519 413 724 498 742 466 611 407 600 511 981 865 955 487 27 622 305 535 257 755 389 910 43 550 206 427 375 516 673 429 570 178 735 498 177 145 7 374 403 471 574 946 43 645 661 127 437 679 618 770 344 54 400 331 937 905 621 61 183 760 235 38 273 370 159 310 943 617 638 773 960 412 297 765 882 511 402 835 358 499 993 458 329 344 549 352 800 840 136 254 952 82 55 805 48 33 787 565 758 222 832 212 570 677 731 467 275 771 883 357 980 639 351 126 435 345 626 566 710 113 929 653 568 286 918 943 583 368 162 943 801 105 426 615 150 325 194 42 494 202 961 465 445 779 784 432 763 197 731 954 675 665 96 790 184 280 183 541 72 321 382 387 726 884 122 373 392 835 69 122 552 74 989 749…
Output: 718832

Example 2:

Input: 742 757 390 309 625 156 980 946 643 746 173 599 806 318 831 810 581 37 121 839 355 155 789 166 59 418 56 824 256 25 723 779 467 540 194 365 810 540 729 378 157 24 169 74 586 432 357 568 255 754 768 722 248 975 238 846 438 722 668 317 314 484 701 997 494 962 482 695 600 971 11 825 54 705 795 72 77 772 826 238 262 14 822 416 537 61 568 878 507 242 809 643 174 453 765 163 804 661 965 589 273 794 226 779 361 205 96 415 398 77 107 527 352 137 270 739 418 562 934 200 553 115 528 738 85 437 298 427 630 402 587 228 959 340 909 547 329 416 198 732 24 405 557 177 982 163 127 930 118 296 845 552 914 829 466 256 220 538 210 530 530 762 154 33 950 969 873 614 687 6 675 162 133 176 620 920 355 496 276 718 224 762 569 409 61 108 996 57 835 700 360 730 862 94 432 827 710 636 194 98 677 614 656 641 520 327…
Output: 367735

Example 3:

Input: 2 222 378
Output: 0

Constraints:

1 <= n <= 2301; 0 <= a[i] <= 1000.

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