CT60826

Cyrus's Ledger of scrolls

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the smokehouses of Brineport close for winter, Cyrus must finish the scrolls ledger - one figure at a time. 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 <= 2800; 0 <= a[i] <= 1000.

Example 1:

Input: 2188 741 788 703 641 272 215 626 80 608 323 584 203 377 163 717 1 835 570 746 456 837 944 230 191 582 615 70 183 530 404 794 783 61 549 307 600 659 614 921 754 267 369 850 54 746 315 998 472 277 189 572 592 551 150 71 667 661 980 326 787 760 750 156 91 189 881 706 955 905 357 99 765 652 359 768 135 837 320 21 622 279 321 826 397 151 201 935 174 794 264 854 503 674 652 727 787 291 945 740 902 970 505 283 925 806 882 852 55 848 904 849 979 325 573 74 833 636 245 455 974 230 961 511 567 480 924 508 672 652 456 102 830 495 78 164 248 5 863 433 685 908 926 816 706 5 317 957 943 282 186 92 355 21 73 782 916 31 672 769 767 990 112 507 183 784 564 852 51 472 712 868 485 455 944 440 543 668 365 5 362 869 206 774 335 81 194 976 795 872 647 668 856 381 240 45 743 878 888 985 696 950 3 977 784 214 728…
Output: 1076476

Example 2:

Input: 772 780 7 364 678 351 325 319 363 24 873 148 967 962 824 811 680 697 257 957 987 993 360 188 251 604 378 989 388 35 945 802 556 873 892 875 889 16 480 280 362 981 433 957 491 550 770 883 274 878 353 826 427 2 908 602 312 332 434 386 325 276 893 674 393 49 337 20 446 275 453 979 201 562 469 115 304 978 653 931 834 923 305 192 896 473 983 38 710 2 890 208 968 713 95 79 659 29 550 860 793 770 433 531 888 841 394 745 175 176 452 893 780 516 503 295 601 964 688 248 173 521 456 666 64 595 504 175 87 381 506 185 274 988 524 147 198 227 394 884 900 807 782 799 897 927 476 719 11 610 89 384 750 335 189 802 660 440 185 675 704 495 974 420 325 162 51 976 699 990 53 356 689 958 246 721 122 946 810 649 294 541 917 497 847 32 399 803 869 967 30 44 625 381 904 765 786 571 573 590 113 276 305 887 841 600 …
Output: 368793

Example 3:

Input: 1465 508 568 308 948 103 515 787 270 854 167 314 860 915 194 355 107 898 998 294 889 306 550 468 391 715 100 308 570 280 505 650 597 353 775 311 575 971 767 602 251 534 519 514 885 768 85 481 930 711 180 946 518 9 158 170 694 353 84 463 565 726 580 330 419 524 923 81 965 768 62 248 866 542 230 3 281 994 896 399 565 24 642 197 728 872 878 269 290 857 215 770 590 491 282 94 748 718 316 683 738 141 811 730 316 21 544 102 271 831 130 95 270 289 180 567 465 819 172 472 772 24 225 896 563 781 323 723 75 596 264 900 496 217 153 955 963 968 866 645 895 5 117 554 609 223 653 161 301 576 114 694 279 778 905 524 439 719 365 243 867 128 758 686 579 161 377 54 140 384 203 366 70 199 829 908 730 546 851 153 915 14 668 915 805 18 494 669 594 357 73 949 429 224 641 417 669 614 914 727 642 826 719 613 785 …
Output: 733338

Constraints:

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

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