CT53686

Zane and the Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Zane found an old ledger of panels in the fish market attic at the otter slides of Sleekwater. The margin notes pose a precise question. 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 <= 3703; 0 <= a[i] <= 1000.

Example 1:

Input: 977 408 518 16 521 813 102 161 59 224 500 893 736 254 918 344 587 410 182 199 75 659 219 615 56 757 169 768 879 430 816 646 110 217 191 749 363 98 206 456 326 115 982 416 136 177 169 899 279 714 366 222 342 502 119 35 2 433 362 776 231 227 83 494 97 321 820 642 650 713 577 616 1000 521 43 734 698 132 268 903 705 269 816 371 441 108 770 733 540 890 53 671 105 772 206 810 343 426 25 909 892 100 10 147 535 969 565 66 990 880 278 787 90 74 117 367 166 162 146 540 904 301 525 879 487 529 266 827 338 694 42 488 199 409 836 842 166 290 880 823 164 297 205 577 349 562 177 834 942 11 839 584 533 405 524 494 520 548 194 88 561 121 337 758 547 442 245 404 774 204 103 565 879 690 73 572 96 63 627 813 134 198 363 593 942 802 68 908 204 480 390 733 40 872 234 955 909 545 848 887 265 391 293 219 50 721 6…
Output: 487223

Example 2:

Input: 284 202 321 146 759 787 183 129 704 802 92 427 961 425 812 215 241 82 728 701 919 248 968 667 248 26 812 957 293 469 530 340 278 186 266 288 280 318 460 378 410 715 819 634 919 856 900 854 932 421 614 185 753 547 946 415 409 43 375 621 294 89 118 649 982 164 867 964 276 973 33 934 884 326 389 205 519 863 602 325 698 992 593 466 78 185 965 923 8 935 733 967 939 220 510 558 865 414 287 306 991 2 132 126 312 513 425 321 933 335 836 988 850 631 33 491 182 768 571 884 659 969 509 123 151 124 375 171 12 931 519 29 176 193 391 167 250 779 224 403 374 594 552 453 267 605 43 973 733 316 342 881 980 327 21 10 137 278 710 469 598 769 716 598 891 148 243 618 322 219 566 999 14 213 918 176 816 699 438 254 242 410 131 723 92 617 876 891 29 345 206 71 538 901 942 330 398 192 454 121 538 822 632 117 449 6…
Output: 132495

Example 3:

Input: 3455 914 990 196 849 629 3 392 281 223 520 613 591 321 623 443 485 603 212 640 437 478 743 482 238 223 307 164 968 608 69 701 304 578 514 445 114 371 521 728 752 22 472 812 576 74 424 71 754 440 676 915 148 280 464 213 157 31 303 635 844 450 417 271 970 93 338 939 610 549 62 74 124 402 601 345 422 516 172 944 861 484 111 848 941 156 281 351 288 1 148 320 12 331 188 689 262 37 980 309 268 453 713 388 25 282 336 414 780 580 708 510 271 105 749 277 650 300 347 340 187 576 31 731 481 958 234 978 19 930 799 501 945 877 702 648 94 782 741 577 183 316 583 79 990 190 28 851 584 522 740 476 239 442 382 487 542 509 125 537 774 0 298 201 533 705 801 382 133 807 958 546 569 529 812 3 980 563 541 246 256 516 227 422 520 838 178 411 177 184 714 298 842 672 34 527 898 102 788 963 978 283 541 316 973 642 …
Output: 1726083

Constraints:

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

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