CT39922

Hugo's ribbons Rain Ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Hugo runs the mint at the observatory of Starfall. Today the books show a list of ribbons, 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 <= 3470; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1687 82641258 940797938 585432519 223670446 377934348 249537044 288861142 112969430 555543226 493709399 593800726 829875399 280247774 635356691 278150223 699863875 962188722 278133432 491989706 230492230 447615274 394667553 798804482 615678411 147485127 845570122 133476512 766880868 553901895 906062884 522569270 820944813 901185387 258571447 898598864 444674277 510299791 691770491 622513690 988615739 348638853 415972952 184135778 305209113 188311435 986911503 781476527 118018511 524525293 369884794 270366595 876764154 274937557 603069290 428680543 429531079 203335522 833689675 789894257 581461842 19386018 964769257 26296419 61912670 806705508 119421651 217371318 780095499 139618224 30195809 87520115 500114125 575209353 243469946 473885611 913229268 89724268 606953040 731556987 48239573 737…
Output: 858469039599

Example 2:

Input: 3157 71157038 697708000 653064167 549249504 391740769 373285969 460427951 334692789 392343995 874827324 443119347 210832730 189972014 752478898 901656820 901849555 530528101 116841257 798341888 59368902 931181154 606887287 381132901 83450281 853589517 174677350 108195497 512575042 563505216 179780794 401732109 85379003 998917140 644509484 504540546 237101639 386569754 214953240 45325776 979569150 290054153 642316168 335968982 829434976 21576147 909322947 398275748 746183841 71111432 13708250 693222835 161687026 436226779 839754079 610377887 960572336 300046208 876853685 254435167 225205942 827007321 645370188 174107820 650558781 865911554 997001497 287881004 266479374 617409232 218715658 47515307 753570858 347299701 966721491 834955769 738529482 457454320 22604098 487524460 238895078 31682…
Output: 1577005898243

Example 3:

Input: 2239 443680416 449509685 962891403 626069681 741066653 993262070 448419419 898175487 833478399 711132730 580038781 702162658 129757131 43199188 204618473 880492010 107431779 175450763 977952456 999798746 682402899 371942318 644763691 387066790 624146116 81505985 196102153 500944531 346384559 278042511 622647016 741800452 188855832 779894298 203155577 386397644 73179063 318172543 791374526 27342195 924446072 293535890 495433958 308693537 177071696 862631542 375163047 809592459 410458094 38582120 856761605 627546057 730904477 98943641 280698209 807374151 911359634 849421143 634968338 713975946 70134775 838878357 79291890 955110637 50968037 300172371 165960185 955150002 520485837 195492414 432847898 81850261 330477392 432757167 287531154 464575988 856151979 105420469 577394816 746031496 94731…
Output: 1116558382800

Constraints:

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

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