CT52483

The Rain Ledgers at Applerun

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the orchard lands of Applerun opens only for a perfect tally of stretches. Rohan 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 <= 3076; 0 <= a[i] <= 1000.

Example 1:

Input: 1060 354 686 573 470 529 448 931 279 704 16 604 437 300 253 584 345 975 592 442 351 203 842 820 908 444 316 571 312 414 556 819 680 23 423 28 952 738 161 698 409 797 584 113 851 450 248 353 770 235 680 465 231 404 354 283 923 725 796 979 281 939 634 290 943 168 192 658 939 253 455 651 789 252 933 407 236 826 594 280 253 841 921 946 781 913 189 682 6 707 406 406 579 992 210 644 476 516 257 777 866 880 249 190 757 444 694 810 349 347 731 675 279 221 703 181 1 25 560 525 319 434 904 824 46 530 491 943 648 817 35 568 584 304 36 154 404 53 359 678 541 812 151 467 501 781 600 892 999 237 72 800 736 842 194 708 598 109 660 919 549 539 586 138 686 765 707 345 6 764 471 386 222 528 848 498 208 168 349 952 938 862 424 649 237 481 130 533 133 269 613 435 186 171 864 643 878 451 658 552 824 608 581 82…
Output: 500462

Example 2:

Input: 2405 338 894 410 750 971 706 90 147 576 218 952 807 354 249 255 315 159 813 548 686 847 258 74 827 580 181 943 601 347 111 662 186 698 176 335 699 176 859 38 343 108 426 218 332 489 319 982 843 712 184 728 117 239 106 606 305 838 752 698 419 881 135 625 496 53 907 295 965 127 820 911 102 768 660 469 269 741 827 589 850 214 132 960 186 670 207 123 411 577 461 296 774 587 473 569 97 690 416 84 973 897 586 587 975 649 6 477 336 51 473 281 261 281 533 40 988 271 603 615 166 39 603 465 595 577 421 636 786 190 409 425 670 358 862 882 639 881 258 576 784 268 90 506 601 759 962 834 124 674 621 836 131 919 47 514 267 705 800 322 312 526 958 269 794 29 106 424 84 788 926 687 608 843 482 807 601 527 93 820 997 628 257 243 873 539 344 305 304 790 43 740 835 344 408 866 901 948 597 905 225 372 228 665 …
Output: 1163657

Example 3:

Input: 1609 777 696 144 523 811 25 251 914 36 681 209 312 754 514 485 209 881 441 922 559 585 127 532 850 634 558 557 478 26 420 302 440 365 986 703 984 53 831 459 426 301 519 365 287 724 447 100 425 359 364 784 140 651 869 538 972 758 35 293 885 40 233 29 569 79 770 434 453 246 881 381 721 76 9 370 935 260 179 587 51 436 38 758 324 843 535 108 780 582 743 8 381 779 382 492 302 912 1 77 359 36 30 791 429 851 255 287 997 132 942 609 703 809 837 864 583 706 774 201 707 235 966 82 946 400 868 574 373 428 106 605 940 303 260 432 837 709 786 62 1 462 178 3 270 65 201 3 937 731 125 970 326 654 882 599 171 40 887 809 17 111 328 12 323 906 597 190 250 100 442 988 665 659 948 428 504 57 444 244 238 5 439 923 110 9 585 838 710 867 818 947 220 713 672 453 885 524 354 694 271 135 841 171 298 757 724 593 564 …
Output: 776143

Constraints:

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

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