CT60435

Last panels of Kate

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Kate the surveyor watches over the peat bogs of Mossgrieve's stores of panels. A careful computation stands between order and chaos. 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 <= 2004; 0 <= a[i] <= 1000.

Example 1:

Input: 1165 903 506 798 775 2 322 543 191 345 611 637 315 809 235 443 635 577 669 912 120 799 640 208 185 224 753 592 725 97 401 969 43 157 62 583 315 46 0 502 85 121 686 741 345 755 133 916 497 648 82 766 794 582 762 683 941 401 517 807 573 400 363 173 316 32 638 578 290 366 645 207 439 551 532 508 94 422 224 672 197 703 915 726 850 911 937 872 329 499 612 763 805 460 783 305 767 437 866 118 68 399 493 967 775 616 946 264 892 919 216 100 219 794 650 563 681 108 790 265 533 675 233 898 379 31 603 752 808 458 728 665 100 902 185 248 753 809 558 978 58 386 950 637 179 586 119 533 352 756 241 87 956 74 171 141 853 740 770 549 524 357 801 691 940 777 696 778 348 928 670 660 85 791 268 373 357 154 279 543 311 727 476 858 504 545 988 739 937 530 471 143 611 23 209 547 430 920 604 272 829 14 70 912 960 …
Output: 560240

Example 2:

Input: 1802 68 105 778 377 543 166 551 68 552 42 158 667 523 233 998 505 458 649 438 176 930 927 362 65 401 425 72 759 936 678 777 704 223 423 235 346 813 95 178 575 815 735 982 850 144 775 948 630 433 855 468 901 787 490 950 606 743 933 650 32 46 503 481 299 299 668 870 203 322 995 172 603 534 487 12 100 573 496 631 296 733 137 710 909 582 991 597 802 591 835 539 395 194 470 838 532 261 196 903 117 104 459 227 728 860 272 98 816 108 157 212 212 650 26 218 25 364 698 597 596 951 118 895 628 768 438 121 541 523 607 555 118 963 536 524 924 833 170 892 544 289 505 992 497 863 401 135 430 895 864 492 443 590 735 853 639 411 820 868 304 549 262 143 442 497 799 638 965 305 550 849 406 58 597 270 262 14 259 738 308 733 448 169 54 734 22 769 176 625 193 905 153 537 129 548 822 395 664 609 703 783 467 281…
Output: 881683

Example 3:

Input: 783 698 277 265 237 346 934 333 688 45 325 62 377 354 96 38 185 218 477 606 119 282 207 836 354 154 314 979 385 886 232 117 921 214 636 154 609 615 758 923 636 133 878 711 243 517 419 377 302 675 989 959 91 923 402 353 878 411 422 801 272 604 103 347 102 972 103 935 636 528 197 409 709 522 912 13 69 95 757 663 917 376 721 579 550 172 277 853 776 774 70 234 809 336 175 828 1 348 323 729 111 481 668 832 190 645 289 912 187 536 428 319 464 390 905 48 981 365 44 518 759 560 86 448 75 592 597 253 800 978 418 47 1 703 224 374 136 690 914 879 238 245 466 780 336 737 683 308 1 215 445 1000 267 252 351 683 9 714 770 394 670 893 375 792 363 654 740 256 589 285 630 911 462 581 869 124 939 918 129 94 183 968 715 914 938 234 691 967 543 926 89 984 908 600 92 192 46 52 186 307 839 75 738 316 983 360 43 …
Output: 381703

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last panels of Kate - MEDIUM Coding Problem | CodeTikki