CT57823

Minstrel Counts the stretches

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Minstrel the chronicler watches over the orchard lands of Applerun's stores of stretches. 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 <= 2955; 0 <= a[i] <= 1000.

Example 1:

Input: 85 348 35 847 300 902 976 642 575 777 438 491 997 708 325 429 524 665 843 111 733 711 194 576 903 867 862 941 333 673 166 517 414 995 539 306 845 241 602 353 768 807 109 193 356 519 801 461 30 631 293 975 112 206 558 918 229 749 717 166 395 677 789 506 908 817 708 555 384 99 638 687 969 646 593 336 54 485 135 88 530 443 977 861 907 835
Output: 34238

Example 2:

Input: 1857 9 795 413 570 20 380 16 571 432 539 159 182 605 580 518 278 61 375 755 410 317 908 635 389 869 954 112 207 918 556 764 545 122 591 822 503 573 614 348 942 808 426 665 882 629 47 330 593 57 242 503 977 854 25 835 111 792 32 948 417 20 417 425 490 200 729 531 500 795 273 785 295 611 9 978 217 778 695 20 895 361 312 532 226 181 582 699 318 396 792 43 716 711 663 252 168 101 548 137 967 759 739 878 560 115 896 852 345 858 634 141 449 76 741 985 52 121 974 792 962 557 630 990 61 512 259 742 176 444 791 359 564 274 217 260 231 53 728 135 415 763 222 485 694 420 309 340 264 750 145 45 793 934 883 509 289 160 331 851 421 583 658 511 278 804 514 371 658 471 839 849 412 846 50 919 603 696 391 934 876 785 680 218 566 416 71 651 147 481 145 684 85 694 556 329 167 148 101 112 110 683 562 466 624 5…
Output: 917952

Example 3:

Input: 87 49 45 244 841 367 333 203 554 821 517 294 124 498 48 868 276 231 803 78 793 271 15 784 504 885 852 450 724 145 238 344 681 830 879 26 313 102 564 168 409 266 378 561 564 890 279 662 464 297 341 657 475 651 33 803 125 362 852 639 536 71 45 522 998 735 348 577 531 623 99 454 184 616 157 101 960 97 517 44 984 303 670 986 933 236 364 445
Output: 35277

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Minstrel Counts the stretches - MEDIUM Coding Problem | CodeTikki