CT61524

Sara's Ledger of stretches

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the gull cliffs of Screech Point opens only for a perfect tally of stretches. Sara 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 <= 2301; 0 <= a[i] <= 1000000.

Example 1:

Input: 1643 231896 974878 667979 353739 48898 870264 206146 559966 862301 678811 330326 711678 498625 740053 531965 518178 69320 860152 426900 940108 642053 832525 658789 171502 216719 596235 236581 858550 873709 901798 932349 184917 663120 901944 437739 909166 804105 939476 286759 938185 98856 594780 461645 545163 807566 419003 354771 218320 558057 44526 262097 242664 58034 362538 307714 709974 226907 593210 154785 449330 812801 174638 865284 377816 137628 312701 894107 732778 591434 677166 903366 712022 520007 321783 360348 109844 358224 634454 953945 332455 513446 514727 990747 794660 647528 193897 421397 739016 765826 732405 902807 697932 989579 66935 451274 951531 522253 675830 716367 101532 350765 213770 307851 463340 179169 703126 724062 296571 707220 76756 618610 141562 280914 227461 6568…
Output: 834331640

Example 2:

Input: 131 157359 826791 685998 357052 367778 792974 257884 47319 205831 44550 523441 359703 687584 2335 288008 842937 899496 467906 702206 965395 816662 275371 36754 840169 511700 913649 819816 914278 241037 631721 111955 109330 993463 593851 886408 80696 366034 440625 673233 955566 591974 933455 455039 677610 135037 953896 882267 629494 726837 929963 844195 481694 449681 622640 237918 840888 643258 184344 517215 255549 641955 709508 830955 10834 253369 57323 266692 108784 5980 163095 157276 469324 845201 665409 417020 984549 200054 305302 292695 695756 759391 303988 724208 269402 952860 255691 27351 141231 935067 612548 395318 272988 280759 812908 658726 887751 105985 80580 312624 532298 37521 514985 531843 26147 788849 973043 804871 876325 481365 840900 656927 939583 777785 807822 457152 71777…
Output: 54517424

Example 3:

Input: 1642 956416 557103 292573 257374 80469 900251 661643 59388 909593 579018 546001 157315 419055 747700 515230 755689 285721 602177 518828 691951 412337 328170 6500 254143 81962 159715 538346 134545 103773 936007 437188 78708 831284 526835 317103 431530 959778 897902 485191 675457 341286 442210 558588 205536 415566 958874 580431 538971 394308 775840 852113 612737 551196 278206 626653 65701 170856 992211 712019 867583 169555 472746 806568 350096 26329 47972 24111 251099 78583 548379 507599 784237 429062 236813 825421 569476 561645 981146 199130 169414 673835 14873 162675 29178 147358 144385 996733 411604 832864 951118 122344 418810 175262 643132 181637 557605 930131 60448 728056 515710 407790 847367 819907 547315 856574 116430 847743 195194 717134 357218 941150 465435 829793 769591 242694 8309…
Output: 812210585

Constraints:

1 <= n <= 2301; 0 <= a[i] <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Sara's Ledger of stretches - MEDIUM Coding Problem | CodeTikki