CT38949

Ishaan and the Sunlit ribbons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the silver mines of Lodebarrow opens only for a perfect tally of ribbons. Ishaan 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 <= 2831; 0 <= a[i] <= 1000.

Example 1:

Input: 510 823 214 513 893 946 322 609 432 743 132 590 261 860 56 329 896 275 502 380 101 114 920 765 451 48 421 964 70 281 581 176 903 663 921 358 278 70 25 58 946 8 126 909 99 143 446 470 385 849 969 88 702 883 934 620 252 172 980 725 898 873 300 747 730 205 418 368 951 398 969 73 564 798 465 639 372 546 11 854 20 778 474 325 846 911 90 122 476 218 570 229 132 342 984 806 885 952 508 573 794 147 554 555 24 479 715 678 751 943 421 453 1000 797 507 224 291 269 955 888 939 799 186 662 472 605 909 85 714 119 848 625 435 102 522 117 877 265 480 661 489 739 108 388 500 536 933 630 992 591 673 642 943 197 843 52 948 547 22 587 676 27 620 156 3 717 100 631 720 483 745 554 497 504 322 620 30 956 73 963 163 837 145 817 440 326 652 982 909 50 861 216 357 353 2 68 40 808 63 982 705 166 659 524 993 557 472 …
Output: 248222

Example 2:

Input: 2818 101 581 43 386 453 543 482 488 156 544 401 562 788 810 948 554 800 366 569 432 315 548 501 848 626 61 994 544 296 334 665 911 967 100 803 278 783 822 605 239 779 775 966 597 888 227 785 156 882 912 452 494 315 402 920 986 421 790 459 138 409 259 997 739 715 182 202 552 63 655 858 760 165 738 870 343 419 77 731 982 425 208 719 679 458 627 34 249 787 429 556 989 70 460 758 685 547 321 772 325 70 516 963 390 959 559 179 180 963 854 675 2 320 255 652 449 775 877 600 377 58 569 982 275 866 18 660 913 129 128 583 502 3 834 353 924 895 284 992 831 686 462 564 340 863 500 241 68 110 603 168 832 473 450 340 732 946 875 284 393 552 122 870 540 734 766 624 577 519 700 254 332 572 855 925 943 570 223 740 562 534 92 93 521 933 875 378 541 237 190 228 175 220 544 25 984 441 724 50 157 876 965 295 7…
Output: 1364603

Example 3:

Input: 2133 571 797 648 602 549 819 756 887 880 953 168 599 371 78 942 249 151 777 553 741 224 887 0 842 562 552 508 336 579 68 301 266 998 891 97 647 461 551 27 864 23 962 734 494 472 689 341 628 372 602 535 858 960 910 755 886 5 108 223 287 957 868 747 624 978 27 521 573 1 794 604 482 276 254 420 185 610 712 486 770 75 111 572 864 738 911 631 619 911 473 803 173 865 356 632 765 739 160 380 697 955 843 414 286 292 31 654 400 917 60 999 500 85 652 738 509 841 402 879 68 343 607 747 166 950 407 84 279 282 826 736 793 342 30 354 475 996 200 96 976 302 294 200 489 774 692 364 47 226 826 21 476 977 432 201 886 701 397 192 632 747 857 755 37 430 628 255 113 490 380 714 879 10 194 979 607 296 212 968 927 181 537 949 301 917 472 800 809 308 591 102 632 287 904 682 146 276 534 798 833 64 243 447 182 571 …
Output: 1037423

Constraints:

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

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