CT59266

Jatin and the Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The bookkeeper Jatin has been asked to prepare the guildmaster's brief. On the desk lies a long table of segments readings. 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 <= 1218; 0 <= a[i] <= 1000.

Example 1:

Input: 73 710 549 261 505 444 109 576 246 418 680 516 427 557 383 442 348 545 770 683 679 816 497 7 177 864 562 681 945 92 956 496 239 110 537 242 970 948 793 810 317 210 532 696 460 996 950 330 992 211 516 900 520 908 412 854 824 179 755 922 832 687 651 405 824 650 141 409 370 906 386 669 813 159
Output: 21388

Example 2:

Input: 240 987 557 174 626 952 76 21 325 575 122 152 606 950 762 544 818 107 908 668 779 131 470 683 295 235 602 60 221 148 130 831 797 182 446 158 500 603 61 123 18 171 883 930 230 314 195 903 564 61 945 484 495 266 663 370 663 645 752 160 792 968 258 718 375 77 328 352 85 913 908 141 66 437 175 585 564 746 687 209 116 152 185 352 351 250 309 616 187 468 309 971 283 351 103 106 195 807 409 122 647 714 672 991 118 429 229 273 848 239 71 435 783 454 7 722 848 145 316 261 918 979 620 438 309 879 819 679 917 21 497 427 166 495 160 556 95 803 929 622 66 423 53 142 456 97 673 429 969 373 605 216 833 575 200 494 416 854 151 467 911 466 809 733 374 605 839 979 780 872 197 518 792 911 516 716 295 834 673 113 602 384 336 584 174 492 45 647 102 850 128 215 815 526 360 660 452 886 590 411 459 577 342 474 77…
Output: 115646

Example 3:

Input: 1001 949 906 287 615 378 479 791 137 444 615 336 450 920 822 233 815 643 504 355 318 958 128 480 458 360 409 424 934 801 321 275 758 415 332 232 875 835 355 31 926 976 488 34 859 810 661 279 480 736 369 579 126 89 21 614 986 234 943 51 797 159 798 992 572 688 903 588 458 367 605 535 452 178 734 308 806 423 437 152 89 657 316 289 985 810 453 533 195 937 864 624 164 104 110 800 896 455 772 119 857 310 60 540 998 69 628 93 169 210 28 47 384 660 463 99 541 682 847 407 163 810 794 855 517 794 190 255 61 899 577 614 920 922 335 294 392 533 850 715 489 621 653 162 526 442 122 814 901 439 33 745 414 181 22 659 813 899 336 190 696 369 727 577 321 758 765 727 154 168 262 373 792 771 948 321 578 706 535 818 409 524 891 862 630 636 555 22 266 405 718 725 963 512 1000 496 597 468 838 32 948 820 543 76 …
Output: 497819

Constraints:

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

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