CT48871

Theron's Marble Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the ivory gates of Alabast close for winter, Theron 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 <= 3618; 0 <= a[i] <= 1000.

Example 1:

Input: 3394 161 532 640 266 933 452 180 390 393 86 320 121 983 207 311 747 873 28 985 367 771 152 226 775 330 758 439 522 442 311 226 85 63 275 741 946 37 989 211 463 1000 551 771 915 134 521 336 876 912 652 796 82 658 183 616 181 789 677 483 980 826 926 911 35 333 525 753 282 564 918 247 301 488 747 860 12 376 17 552 370 634 263 943 227 556 638 562 931 109 479 831 697 581 527 46 97 720 527 143 816 614 841 360 360 405 459 535 538 637 675 26 927 337 244 707 805 493 896 292 261 483 630 365 888 838 294 156 257 928 231 176 68 673 165 466 830 69 904 571 973 642 890 18 431 117 35 154 220 411 818 680 921 318 419 236 741 162 960 196 966 482 955 464 546 166 517 93 693 203 204 818 264 535 694 21 734 219 205 996 650 580 871 528 383 296 967 810 175 783 265 308 434 365 882 350 772 235 504 912 986 716 496 365 …
Output: 1716219

Example 2:

Input: 3220 498 772 782 217 307 539 732 873 390 197 891 321 216 465 669 855 556 234 156 53 229 487 808 116 181 525 531 721 81 745 158 783 880 149 283 287 823 439 380 173 218 997 266 67 634 845 897 12 6 215 820 724 610 200 45 102 51 691 402 537 241 781 933 226 441 297 349 751 488 748 695 720 554 19 704 71 233 151 162 142 44 77 437 674 230 173 517 661 663 430 592 466 190 532 562 847 37 939 552 774 720 174 885 807 323 670 412 965 134 842 441 461 905 591 729 605 400 787 959 323 985 818 126 824 40 862 668 939 616 146 526 807 710 409 776 156 648 189 840 189 876 145 155 858 583 259 463 2 45 59 527 263 194 407 133 568 339 328 654 502 448 980 457 352 80 238 711 926 284 507 867 159 909 691 695 90 681 901 425 384 84 975 224 292 991 342 318 811 202 624 574 767 827 282 75 195 346 185 401 857 557 622 922 541 3…
Output: 1600234

Example 3:

Input: 884 893 292 783 813 160 757 691 864 203 705 864 875 851 165 620 140 20 456 853 930 357 810 507 333 626 19 589 615 946 490 741 966 341 204 326 197 591 664 879 801 23 990 537 678 872 911 217 47 713 877 794 220 363 222 530 809 80 118 65 802 572 303 940 136 718 805 945 205 246 356 7 805 167 524 355 166 841 694 392 316 572 859 786 627 303 66 248 933 436 262 170 269 463 804 501 657 733 901 525 309 680 866 48 241 441 766 855 979 163 918 917 843 828 278 182 602 177 759 106 502 724 6 349 572 710 193 615 447 60 457 880 874 856 784 924 509 675 311 400 199 981 115 791 508 408 835 13 185 430 274 358 642 92 46 899 258 966 825 980 920 904 198 23 514 363 415 119 532 608 926 61 513 431 459 572 507 514 441 979 50 997 151 118 698 245 565 809 654 999 901 835 763 362 769 398 546 629 593 2 24 280 545 566 46 460…
Output: 426677

Constraints:

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

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