CT39732

The Rain Ledgers of the Woven scrolls

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the ivory gates of Alabast, Porter records each scrolls in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3745; 0 <= a[i] <= 1000000.

Example 1:

Input: 2607 527849 141967 359167 665786 238734 882963 80789 704513 964762 255139 888280 282484 588102 451446 550830 872416 606629 500922 983125 57247 660559 649094 719057 322138 869219 630003 439645 271931 640143 871343 488961 901503 814538 93645 28401 888965 102467 479976 81651 322714 628100 519601 601389 33971 439247 610128 346032 860499 644788 873966 745911 305486 896150 173068 961174 479707 593093 800942 729946 876051 446891 426576 28467 876082 87958 794862 578717 668725 770 122911 49245 786978 503712 575855 482632 801145 196247 620646 610065 495708 929420 613559 3487 774774 434445 776568 585240 648660 54464 684072 176810 303400 514742 725173 535360 305060 450041 165210 270958 181397 835891 983020 277436 893872 435954 803457 950211 261061 972871 609463 269246 792477 261747 636358 738931 27030…
Output: 1288304319

Example 2:

Input: 3512 867655 531580 9714 353866 448985 148564 638046 821510 587124 659969 318131 433482 238679 301910 595379 986721 741546 293235 481249 389594 593912 32150 533713 783670 262755 5899 200836 733931 827336 764552 532796 352762 644031 878755 3829 708374 770606 765778 476115 258938 501471 130818 2963 708763 116697 464958 549862 253201 72794 153358 235942 508497 338483 799391 138521 498160 101410 539499 969515 989825 230834 587262 845269 718586 482863 239456 262228 683229 788084 846664 456173 248601 410007 913121 59872 272094 296324 523217 742984 642541 128009 9290 433655 470161 104336 259862 808480 770966 524746 445462 346449 356193 912153 400974 789022 726717 630617 116900 332008 658574 818758 610272 80968 356432 360431 269537 806473 50712 887495 610981 282804 166092 714712 363929 854764 47983…
Output: 1761845426

Example 3:

Input: 1065 409170 923072 641740 989668 132986 28205 485733 401319 879562 901263 731946 970416 896970 243761 607305 86163 463263 868297 855036 114973 150038 137980 735941 840197 529204 296963 698317 181128 147248 997571 343166 503672 126389 634261 303851 162346 386442 547171 953086 277382 156141 815152 50329 299964 831415 585938 991014 533053 829276 114077 919554 710321 768845 533924 320753 461807 165349 407861 986274 744321 426185 424923 424541 145292 831170 956533 88472 208199 657391 94203 481144 218637 544013 6190 426682 913338 761337 147605 46288 78113 975499 15559 640233 734458 618576 641369 527924 781473 924798 531293 542243 536624 767510 411473 223548 224075 172230 310216 607730 277478 477958 615181 308373 560934 731648 13129 506973 960869 979316 263505 303763 811851 280733 70986 692780 12…
Output: 516100644

Constraints:

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

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