CT54509

The scrolls at Redrock

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the canyon post of Redrock opens only for a perfect tally of scrolls. Draper means to find out. 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 <= 1160; 0 <= a[i] <= 1000.

Example 1:

Input: 129 19 975 782 683 413 70 380 270 310 600 839 382 899 878 471 166 622 681 248 944 783 811 480 845 714 147 341 491 740 331 983 950 683 855 218 662 99 577 481 990 170 591 23 88 57 372 537 402 25 714 251 468 463 68 240 239 78 914 293 373 671 982 544 177 141 494 949 109 854 217 613 95 439 281 975 447 890 71 51 856 648 88 913 955 487 425 657 500 960 521 295 997 499 412 662 874 415 751 52 162 953 509 518 414 113 966 993 779 474 318 14 639 229 670 47 366 176 190 787 879 348 710 293 115 808 817 930 444 179
Output: 58750

Example 2:

Input: 1093 0 199 648 891 154 736 102 633 305 174 252 558 284 888 926 870 321 904 708 369 468 181 110 923 527 812 12 93 945 115 485 378 145 950 237 106 783 612 166 602 252 179 862 174 974 380 274 335 317 147 586 261 342 441 955 622 705 691 144 46 250 510 83 375 905 109 489 616 948 225 70 837 861 244 389 138 149 36 568 990 997 536 364 765 161 785 869 640 217 422 359 356 300 668 247 837 683 404 535 372 398 225 153 341 536 107 359 126 828 127 630 256 353 593 68 519 148 52 794 268 924 495 588 488 178 750 207 323 287 152 917 171 687 606 132 168 623 771 793 131 541 145 594 845 521 325 160 773 148 166 731 250 77 741 279 924 547 756 208 293 871 919 901 705 565 567 387 151 464 385 818 759 226 386 268 912 498 856 156 174 369 744 774 700 239 832 612 901 250 970 967 460 181 272 507 398 368 625 257 608 496 76…
Output: 538686

Example 3:

Input: 270 821 295 144 71 871 532 57 977 574 615 205 227 807 367 191 510 360 560 788 596 334 840 98 203 308 937 242 258 568 437 649 185 758 321 475 167 131 732 244 299 631 869 735 6 92 853 710 892 497 24 921 464 622 43 937 515 654 266 904 300 983 924 422 50 127 765 660 297 753 937 998 703 294 315 575 828 72 789 190 778 588 970 433 496 259 554 310 897 56 171 972 637 1 669 633 918 633 227 808 103 678 442 314 545 451 250 565 827 476 463 607 743 173 653 679 393 531 288 328 945 369 496 884 249 822 207 808 742 701 722 96 90 586 22 705 109 386 32 863 255 990 20 480 84 853 472 146 702 143 877 623 984 816 486 954 28 34 149 321 975 961 478 98 968 651 638 603 690 759 995 889 441 627 695 633 212 905 463 224 272 185 188 703 660 396 974 439 286 908 601 283 326 437 331 515 119 416 829 569 325 625 143 470 376 16…
Output: 128437

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The scrolls at Redrock - MEDIUM Coding Problem | CodeTikki