CT55550

Innkeeper and the Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the peat bogs of Mossgrieve, Innkeeper records each ribbons in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2840; 0 <= a[i] <= 1000.

Example 1:

Input: 2094 13 582 702 849 217 311 970 261 400 291 746 318 771 740 311 164 433 570 80 10 989 966 199 730 873 718 77 878 843 635 107 380 248 560 763 168 646 230 915 322 858 165 142 133 51 637 871 617 912 58 45 630 791 858 157 965 505 133 743 322 82 593 444 444 232 493 483 711 10 949 524 253 957 73 970 88 697 881 359 279 182 469 892 979 893 289 911 439 29 676 430 916 80 93 325 457 141 504 422 353 969 502 973 41 784 240 339 62 10 661 658 490 679 561 987 361 557 415 134 263 364 76 971 834 769 508 685 626 122 514 393 978 892 773 315 126 824 738 153 894 637 742 858 270 886 725 965 911 356 882 287 641 532 732 299 466 528 701 943 676 388 891 367 716 74 177 49 773 154 555 873 879 370 61 276 928 362 250 111 215 221 746 785 496 802 778 852 804 814 623 444 458 719 228 458 486 263 734 604 722 189 247 900 493 …
Output: 1048275

Example 2:

Input: 2284 703 997 505 90 764 599 433 140 970 797 681 698 838 535 461 385 607 581 220 532 978 670 106 177 878 376 905 45 436 840 200 345 417 900 965 444 829 630 484 534 503 758 587 666 323 850 491 484 840 760 732 135 543 193 729 505 230 193 657 223 403 905 630 750 172 204 75 618 562 224 27 163 273 336 541 258 695 738 762 882 695 555 3 404 601 468 330 540 765 858 241 74 88 358 175 31 102 325 419 73 582 255 326 605 301 126 975 777 437 775 570 61 993 85 641 796 565 301 223 899 495 161 274 335 384 78 618 597 906 668 580 7 313 987 711 681 42 566 445 158 959 552 578 85 78 636 462 245 344 936 493 687 153 804 376 59 973 104 552 615 358 46 215 379 622 645 813 156 919 18 406 824 4 298 644 269 423 228 413 852 955 247 506 745 975 439 172 617 970 437 135 932 970 507 264 109 114 823 17 599 31 670 110 916 64 4…
Output: 1139562

Example 3:

Input: 1896 129 557 340 131 673 332 167 750 223 926 830 671 296 723 76 103 750 91 901 106 521 353 515 370 697 353 800 553 591 987 565 978 402 760 419 146 697 636 726 678 199 422 590 344 569 66 230 183 325 253 625 933 976 853 706 819 115 536 988 422 246 739 322 129 785 637 587 198 693 294 454 526 781 962 936 523 490 531 720 659 879 936 957 216 286 912 575 505 990 469 761 893 332 44 703 213 398 460 185 540 162 892 451 565 759 373 704 830 675 759 425 370 163 856 252 920 425 112 296 304 559 792 759 930 239 106 776 564 401 25 811 698 492 757 502 737 653 147 586 94 936 531 537 856 832 886 504 182 739 987 323 187 247 413 454 679 439 108 754 683 357 194 295 638 953 735 137 1 133 353 402 27 140 467 400 420 971 165 595 738 783 766 445 112 964 449 393 477 410 748 863 741 466 823 153 435 653 150 887 775 82 9…
Output: 934980

Constraints:

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

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