CT63844

Last stretches of Shepherd

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Shepherd runs the ferry office at the alabaster quarry of Whitestone. Today the books show a list of stretches, 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 <= 1157; 0 <= a[i] <= 1000.

Example 1:

Input: 920 202 511 296 143 893 390 708 399 166 527 738 979 611 844 854 472 616 842 400 613 32 37 522 605 442 860 175 543 572 675 243 549 942 712 13 823 327 837 947 220 251 142 648 938 459 859 553 586 415 237 587 314 158 488 525 926 437 723 984 879 711 672 329 127 871 831 944 556 682 145 111 218 422 933 280 807 253 869 756 443 454 707 994 381 14 134 207 354 75 367 317 161 441 823 494 583 783 653 575 425 293 79 274 804 956 174 855 644 163 460 501 212 279 410 449 869 985 340 88 538 491 348 255 637 323 597 902 531 292 945 491 5 272 366 211 897 15 231 832 110 678 635 270 762 462 358 885 30 400 518 512 129 168 148 549 543 410 732 749 577 948 965 447 369 495 794 268 847 950 13 439 453 830 841 662 712 812 410 454 994 185 511 977 853 268 7 196 32 5 447 291 884 387 829 190 795 76 951 396 66 494 801 492 856…
Output: 451353

Example 2:

Input: 152 952 639 202 860 433 522 412 330 561 353 953 417 82 919 992 726 410 948 396 421 725 706 583 501 667 233 448 215 373 940 85 407 545 459 658 173 482 956 739 67 867 475 31 887 992 724 323 697 945 619 141 399 43 973 917 371 871 875 798 455 504 538 210 503 233 402 432 854 164 518 848 986 968 590 266 535 39 466 41 739 634 311 535 281 161 526 550 578 724 550 739 759 816 297 360 578 927 199 688 286 541 191 653 226 625 487 295 522 286 447 577 979 182 691 846 738 493 380 140 553 944 673 990 105 497 593 789 6 936 905 736 823 623 882 110 727 668 653 62 616 11 288 859 55 264 520 70 228 324 183 588 509
Output: 63980

Example 3:

Input: 287 735 56 502 177 137 677 385 658 660 410 15 850 154 210 448 416 296 856 55 905 296 857 963 648 481 803 808 938 316 244 303 202 171 853 26 868 732 844 146 444 192 106 739 269 576 60 680 280 68 453 953 700 210 391 799 260 153 204 293 179 698 32 314 686 754 652 285 5 539 511 801 212 751 836 508 941 268 130 115 964 621 858 497 157 578 27 641 566 45 146 41 21 425 675 487 162 629 120 954 194 450 690 125 740 595 218 711 359 370 240 973 736 354 283 53 193 663 998 288 707 268 359 682 447 632 224 813 974 130 679 363 70 547 506 657 864 339 846 135 744 647 349 3 742 821 574 571 825 973 687 233 481 492 993 828 980 774 755 254 133 887 785 924 673 508 520 1 226 501 877 815 520 633 372 350 77 869 969 122 288 543 169 323 260 721 810 878 696 11 255 988 25 920 869 654 443 680 40 765 598 506 655 103 707 204…
Output: 133789

Constraints:

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

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