CT43196

Weaver's Ledger of scrolls

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Weaver runs the kiln at the frontier camp of Duskwood. Today the books show a list of scrolls, and the numbers must be worked out before sundown. 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 <= 2160; 0 <= a[i] <= 1000000000.

Example 1:

Input: 582 343272577 203413720 677387215 55716797 666971972 388020108 865004923 831326069 685731329 713705983 20452814 868795539 265818637 369881718 612628607 300589832 8355468 724111585 10171805 886198263 265743492 828648560 900940157 327502787 342426007 986949124 709429666 17752029 554374403 242444814 215027146 75506026 819947133 618482729 928127038 700410259 576483706 370906116 464295913 694010465 447268625 421402165 516555667 248419239 744498088 98964828 217796157 667803339 130932115 973769266 764917172 148280227 795841894 967457797 874731289 944480135 306784689 357523308 536159292 350018679 998267999 456225268 953387845 330501639 431587564 450802474 167459797 262968082 336617506 445516173 901914345 211652797 825796971 414763281 407629089 940022858 733051890 937201712 455015555 637902200 2934…
Output: 286115646105

Example 2:

Input: 716 549852786 843660316 587495160 380931863 431731045 955706561 32810051 93928360 809196085 500595052 692360981 793515758 865791477 571919953 777997417 319121955 883286373 44812692 171902353 863663638 831030460 645434850 44189971 492146829 124810930 587504779 689026028 34467908 222209034 929292113 896963097 933422331 212170159 426931467 586326178 89081429 409135206 25549815 104103842 246738217 56833416 634053841 447867754 685817611 924058092 738153858 224191314 24362808 332026091 900901786 89406281 86850598 398542389 14146096 565817116 791607643 123000580 552853083 929907379 611685974 401958501 232571681 487297943 353444801 774398222 149096687 639382148 730096615 651033938 536687428 638081402 813099365 443076399 262599648 435311258 374065588 354638511 612202631 118515380 395968523 13678829…
Output: 351674318496

Example 3:

Input: 1460 996309445 669986415 616546256 410137174 849493730 509520091 237541409 617031720 642276168 908579835 989554013 841866915 972914669 451715705 888537324 144387202 296833286 252181672 488092788 961033713 879515542 449407092 194918647 55918883 352901496 248319278 416253606 219969207 458496034 651112828 184787137 267169161 54650030 7088835 965495128 566221195 969162827 397357401 831372112 276618294 217685794 741143158 894479894 338531163 531754468 870826360 873822515 583584927 85133486 672383713 694872374 843018652 592202878 638813513 315824319 282777156 524352784 52503499 110502046 945479615 204423740 851576154 709086615 270396018 224793774 833481802 102122551 145472899 779617566 795386695 59170032 302126734 598197393 374734696 956030051 220174918 785203951 838122288 315208614 268175633 22…
Output: 713800857465

Constraints:

1 <= n <= 2160; 0 <= a[i] <= 1000000000.

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