CT64672

The windows at Palemere

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Jaya runs the loft at the salt flats of Palemere. Today the books show a list of windows, and the numbers must be worked out before sundown. 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 <= 1626; 0 <= a[i] <= 1000.

Example 1:

Input: 695 321 690 641 408 749 18 993 165 144 353 692 129 964 231 495 470 164 11 15 276 736 55 817 956 84 738 436 706 765 839 374 669 586 9 249 632 161 223 862 537 54 587 868 595 173 586 414 537 38 746 168 55 893 426 429 587 368 987 143 474 695 651 342 309 209 945 699 948 702 784 731 457 406 708 804 965 963 640 227 290 950 35 214 644 54 735 949 6 208 132 851 316 995 141 273 651 540 627 371 450 551 569 82 797 256 234 860 712 727 125 981 293 438 910 1 472 178 847 952 541 525 342 944 374 15 113 6 121 718 663 614 356 479 852 596 175 998 172 456 798 105 774 274 40 444 229 865 644 860 915 935 408 901 828 379 552 494 768 224 683 898 218 92 688 143 228 375 563 432 489 576 481 912 808 572 289 862 907 63 744 694 865 111 882 795 445 304 952 93 976 906 89 923 326 805 521 922 992 408 309 805 332 899 135 700 6…
Output: 348927

Example 2:

Input: 1612 977 213 24 364 875 639 175 906 941 397 673 974 377 927 772 371 202 77 500 612 256 241 518 978 311 256 209 712 432 509 60 468 925 107 143 591 786 619 230 950 679 623 24 941 302 822 871 526 157 835 164 168 597 638 526 918 12 874 442 659 497 20 535 351 790 619 728 176 997 648 558 472 646 665 439 618 260 366 313 73 567 442 993 201 18 706 356 202 641 462 913 821 144 665 500 442 124 451 239 680 105 689 639 830 154 941 260 302 416 647 123 73 567 639 990 957 917 653 703 693 244 977 631 481 537 234 74 167 569 411 913 301 258 562 355 579 984 57 690 612 445 5 215 915 568 618 758 700 341 702 11 153 59 300 217 140 206 828 227 33 805 215 103 22 693 527 22 229 385 620 353 732 584 690 234 427 488 277 605 993 868 394 451 77 718 858 946 902 807 862 989 938 874 20 489 72 38 584 718 85 612 690 82 404 510…
Output: 807454

Example 3:

Input: 833 6 116 55 244 248 63 507 806 880 72 724 409 538 91 519 751 660 401 399 106 540 449 865 386 830 975 198 534 163 33 986 817 401 634 73 468 431 976 86 827 263 189 671 152 98 602 710 99 103 919 528 304 531 417 260 479 45 533 105 527 784 896 436 570 491 794 814 821 626 424 202 869 263 233 21 197 232 417 998 938 470 821 643 712 43 551 888 351 163 854 395 514 13 426 265 793 276 646 638 550 537 662 82 825 287 28 133 676 969 236 370 750 430 749 59 683 58 477 389 84 594 861 867 871 345 554 606 169 140 751 98 856 818 898 463 938 339 934 761 802 6 639 965 588 553 568 304 786 30 642 357 391 497 615 644 860 825 325 386 396 853 74 69 606 614 819 740 119 392 673 732 497 836 92 575 533 727 411 401 275 370 132 517 225 63 728 577 153 526 483 704 469 363 84 610 220 696 795 441 924 702 17 922 289 778 420 51…
Output: 407576

Constraints:

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

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