CT59768

The Rain Ledgers of Grapehollow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Archivist the tallyman watches over the terraced vines of Grapehollow's stores of segments. A careful computation stands between order and chaos. 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 <= 2968; 0 <= a[i] <= 1000.

Example 1:

Input: 552 475 414 395 864 113 663 951 621 511 932 254 181 30 510 390 318 130 619 180 762 836 631 346 337 192 510 228 127 199 98 19 207 275 544 616 834 517 890 33 537 183 367 130 255 91 807 62 658 529 174 329 838 287 97 177 665 559 836 266 561 605 788 729 609 830 488 889 866 753 714 18 736 380 22 533 343 82 798 658 191 366 953 253 365 414 210 478 78 281 363 377 518 37 462 498 173 604 875 690 955 847 375 628 515 915 887 883 317 92 54 835 511 22 787 858 686 647 773 162 847 868 737 260 500 725 742 983 450 710 803 326 76 979 52 756 640 503 718 345 879 134 134 711 184 248 267 157 122 243 539 753 932 404 409 193 256 858 380 690 291 824 704 756 454 607 37 530 11 913 901 563 345 450 837 823 550 13 261 662 597 994 102 835 186 805 346 658 848 855 830 622 452 676 98 459 910 299 337 199 959 788 588 962 44 42…
Output: 263062

Example 2:

Input: 1674 260 246 328 908 946 70 195 814 318 220 976 686 348 128 558 578 153 437 634 84 982 98 791 602 202 920 969 372 380 289 378 589 871 968 721 831 869 960 869 435 346 407 983 40 516 990 233 773 270 771 7 598 691 142 591 547 271 411 992 556 895 162 540 379 575 641 422 7 939 891 158 402 689 992 201 763 243 404 325 484 426 958 964 760 834 291 101 386 290 580 174 409 22 488 71 624 545 353 359 878 556 537 803 481 357 146 122 205 416 728 956 459 959 690 177 232 112 31 381 577 12 476 339 998 994 957 751 383 311 749 122 151 655 644 56 613 358 646 610 875 680 449 951 202 385 342 620 570 670 89 827 961 317 354 643 111 362 843 450 443 255 656 636 289 12 4 858 768 134 837 611 937 884 961 101 328 357 321 390 327 733 425 244 237 619 890 546 105 839 983 602 852 227 595 295 777 51 324 200 366 718 770 87 54…
Output: 814075

Example 3:

Input: 733 814 315 115 817 496 750 50 308 469 626 965 433 89 997 497 144 88 303 38 592 45 160 912 423 676 731 268 595 708 257 14 545 589 592 663 281 352 906 351 639 67 574 163 129 206 193 399 760 425 201 850 679 2 404 201 961 740 97 690 326 723 714 481 911 721 381 682 767 239 464 213 857 53 496 139 519 874 25 667 1000 731 743 369 161 850 875 863 114 582 833 495 407 459 437 714 139 742 694 307 930 762 740 420 308 986 320 760 606 118 484 4 291 243 428 499 543 148 893 134 129 710 543 426 591 764 908 266 924 528 605 706 570 903 515 150 864 760 517 670 482 199 507 410 661 945 806 620 694 448 479 893 460 949 552 292 343 418 161 554 773 276 283 689 61 304 139 685 369 454 359 259 484 790 582 540 393 194 784 207 987 974 386 986 260 899 752 401 365 384 650 562 958 985 567 56 541 4 42 925 104 585 194 259 54…
Output: 357589

Constraints:

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

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