CT39716

Kael and the Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the island market of Coralcove opens only for a perfect tally of panels. Kael 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 <= 1558; 0 <= a[i] <= 1000000.

Example 1:

Input: 713 408875 113415 296531 73200 455854 938847 104866 757369 438830 772064 605073 906248 601985 117128 691636 768195 581813 972260 510958 633678 249439 348261 801916 440018 799911 982603 86254 740604 120535 366432 355910 419820 981561 501304 858304 43729 348371 34625 356580 177895 649598 583962 394442 539818 843742 203249 351485 413452 965024 313800 701936 9057 111465 44705 6940 378659 934790 469777 661015 182920 48837 427118 135969 99441 482052 943865 909951 149767 112176 654654 461620 182834 643181 767157 634624 687789 740537 370971 727778 710893 797426 907221 141601 618597 348813 772196 796414 409895 581843 783756 399515 878287 697413 59141 784859 910746 235805 979615 882879 627162 742366 550000 764342 887175 880897 881118 413681 444221 614329 751910 798633 520168 319054 567821 686015 600…
Output: 338313819

Example 2:

Input: 1513 918729 854632 78124 125223 126541 403902 197408 631183 654820 661703 188732 942176 960880 33082 489018 632434 912779 763494 135313 42466 619839 980336 857672 848277 183013 475633 868045 549263 150164 161261 767343 535082 574607 592971 990149 681463 582738 209148 899406 638200 26292 515337 716640 98753 473751 422923 158853 576344 908893 950104 865 404667 528513 659971 725524 789105 813389 837556 161045 472015 91959 37460 982063 376110 744993 780923 792526 370339 201409 832901 236683 98236 993435 303045 880130 797399 490486 333014 257165 972780 614536 69004 491295 39658 180300 258672 854249 446393 24902 650125 236726 758653 997644 479415 946455 233899 176246 784046 531117 651534 189096 171137 969726 825090 515940 978298 975032 7773 731451 336356 880013 498183 226426 728816 277059 977482…
Output: 737551007

Example 3:

Input: 247 545987 862389 99863 809956 977215 914389 27254 130351 488664 739718 283066 989943 975440 80117 640325 869721 283431 609305 834542 31418 461359 451779 997012 798461 477370 63676 660197 240987 195322 454389 979668 598672 165032 893945 939279 816598 528718 979387 204247 756643 146435 139370 535762 922866 982106 60554 10904 50810 538180 392852 108838 397989 45656 736099 241159 813163 756600 289586 844357 429974 587828 162267 121734 290885 573896 183059 235460 643774 440922 28962 537913 517550 284232 130412 456033 320817 760222 989243 597703 662772 420978 489822 260064 445417 524978 217445 781945 882068 424631 253336 609015 465172 733516 473374 145471 776672 580079 844436 971767 603817 245565 769213 554312 259214 169823 627265 717142 13222 577169 590091 465437 832806 47572 673938 913157 486…
Output: 119024274

Constraints:

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

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