CT64388

The Rain Ledgers of Tangledeep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the kelp forests of Tangledeep with crates of stretches, and Vani the auditor must account for every last one. 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 <= 1842; 0 <= a[i] <= 1000.

Example 1:

Input: 189 860 452 804 274 852 292 888 294 441 504 894 724 705 487 669 624 922 895 728 709 11 784 710 431 911 547 538 16 34 278 586 29 55 570 485 685 86 384 789 396 879 581 979 676 602 531 764 176 360 172 902 540 404 529 422 491 459 554 200 381 988 135 700 91 689 932 938 769 384 343 888 967 806 121 654 568 531 335 912 733 256 512 558 896 457 460 378 904 450 650 85 127 935 905 581 398 296 170 874 525 198 550 105 22 171 86 37 146 998 775 682 355 730 797 96 588 797 322 726 612 40 107 237 637 423 919 787 52 293 432 704 201 537 490 625 545 123 535 977 687 352 808 142 537 484 901 334 113 453 325 895 418 518 321 10 273 882 584 138 623 197 80 381 260 378 660 998 2 410 192 223 525 383 913 598 640 862 719 624 398 560 968 783 665 470 563 473 925 99
Output: 85095

Example 2:

Input: 1801 673 293 42 820 771 634 543 651 229 178 236 564 356 154 275 126 580 331 573 294 448 368 805 153 258 874 59 495 430 735 331 362 987 40 939 315 335 160 136 10 115 461 251 38 922 261 634 749 955 248 340 151 419 927 425 245 862 850 578 340 416 427 281 426 294 839 895 690 88 103 118 286 321 720 913 807 818 415 536 298 999 276 956 956 99 721 986 646 107 807 586 716 378 224 71 298 769 350 371 200 495 460 983 95 548 787 350 620 954 178 83 330 77 718 926 936 735 513 760 835 0 416 573 492 949 194 500 764 909 686 997 900 825 79 374 290 705 362 577 715 577 939 99 948 114 793 822 849 24 10 417 554 927 278 649 588 584 496 627 741 152 42 251 551 335 400 65 531 775 675 540 446 63 498 994 557 187 896 696 321 361 771 835 937 731 449 234 873 908 777 70 209 577 480 998 310 94 199 864 56 955 320 409 604 47…
Output: 894337

Example 3:

Input: 390 795 908 502 673 641 303 106 573 292 834 114 587 228 908 193 47 152 695 937 104 798 520 182 340 982 555 722 57 157 791 173 982 893 12 145 504 899 439 844 533 125 997 377 362 325 334 180 216 657 586 179 769 681 221 157 530 209 416 292 674 3 363 46 284 255 218 162 785 123 617 645 874 744 324 612 332 482 812 746 605 149 320 516 160 56 48 977 638 445 985 977 31 311 870 509 591 64 367 620 465 738 39 407 852 64 7 737 464 59 147 481 518 408 364 469 416 352 532 145 652 543 335 174 877 811 519 422 648 98 256 466 728 859 156 961 242 554 855 746 237 948 388 375 102 429 955 642 235 252 158 809 732 325 875 564 180 812 132 103 610 789 472 201 102 631 626 112 815 741 433 359 213 405 140 390 132 227 677 382 20 724 205 871 443 398 53 4 806 571 647 524 413 295 971 10 953 813 848 681 422 90 772 222 359 57…
Output: 191684

Constraints:

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

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