CT39193

The Rain Ledgers of Balmcrest

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the cedar groves of Balmcrest opens only for a perfect tally of stretches. Innkeeper 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 <= 2139; 0 <= a[i] <= 1000.

Example 1:

Input: 318 309 78 978 219 409 672 728 394 364 978 31 275 391 980 627 81 172 627 470 294 291 558 268 99 223 220 106 862 360 774 422 791 108 713 850 783 819 326 335 753 641 248 301 706 614 555 828 63 725 551 301 589 811 260 421 988 117 719 50 251 528 947 233 988 492 448 67 270 691 78 221 713 200 99 786 303 998 121 759 679 409 276 207 948 767 522 748 236 96 207 50 383 89 393 409 999 397 19 937 443 959 784 330 638 326 488 145 293 492 797 888 286 357 823 150 359 375 196 896 958 737 155 270 516 509 712 878 705 143 115 859 774 196 955 549 693 325 619 408 270 959 760 495 923 876 776 741 772 301 635 265 679 824 103 905 114 8 344 907 210 261 780 92 526 217 525 194 67 187 148 256 93 114 489 530 82 302 201 529 474 94 882 588 955 832 33 445 551 833 383 184 444 364 450 841 619 890 156 822 763 599 470 428 341 4…
Output: 156220

Example 2:

Input: 1768 620 989 523 111 171 164 240 161 291 895 834 459 396 86 833 673 96 97 134 937 215 653 528 314 590 385 809 71 118 573 266 427 975 547 5 788 795 555 625 523 836 730 877 792 506 14 21 740 328 995 805 327 586 388 603 955 847 806 575 22 111 333 925 197 486 544 817 944 768 470 752 758 278 675 900 503 516 132 853 973 943 828 489 417 749 86 196 584 904 814 575 432 177 703 794 89 21 856 344 393 1 872 161 978 627 806 614 539 655 28 823 338 215 511 768 168 125 444 545 356 785 511 406 790 148 582 810 29 956 935 41 756 851 864 320 325 947 538 436 975 447 899 155 8 584 688 662 13 76 312 202 267 505 272 222 974 668 688 909 972 858 635 279 477 951 260 809 441 417 239 144 388 793 271 249 842 736 181 976 401 430 175 955 660 256 751 229 552 195 548 139 823 537 603 68 97 683 495 72 498 28 807 809 512 425 …
Output: 859550

Example 3:

Input: 227 321 719 763 577 362 294 982 775 392 366 815 480 274 363 288 146 495 87 293 960 987 850 62 913 777 817 812 49 134 180 425 53 525 308 216 137 831 8 829 738 132 229 787 168 753 303 878 775 207 489 755 374 665 293 656 133 482 832 489 669 243 183 303 20 986 306 697 703 858 597 295 621 210 259 538 472 365 491 267 765 371 693 225 64 140 24 787 865 858 7 243 990 477 178 801 588 259 55 265 457 118 895 742 158 52 714 959 1000 32 519 158 127 244 339 452 60 705 718 364 398 877 446 350 717 271 487 856 593 418 126 407 790 919 540 983 243 346 847 757 735 154 101 125 282 796 75 788 453 582 613 431 291 506 560 338 539 460 896 607 737 574 932 22 346 292 590 742 154 327 603 269 709 981 50 709 575 178 589 734 355 24 162 394 497 751 218 748 699 941 290 75 699 460 571 403 676 956 687 221 513 335 576 644 99 …
Output: 111962

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rain Ledgers of Balmcrest - MEDIUM Coding Problem | CodeTikki