CT42290

Piper and the Whispering scrolls

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the mountain city of Highreach opens only for a perfect tally of scrolls. Piper 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 <= 1886; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1670 26240208 329032607 785286619 272096286 498369322 782432068 756883056 93003152 767436830 869206695 216184828 491036685 409100974 215044733 714568293 933258388 185144107 848786070 866782797 433434427 593385678 211713620 423774591 876335612 361611276 685208466 577676192 467785436 660832031 956848818 64065728 94556980 25217097 607122916 106880839 224543462 688822752 206102033 753111612 921414926 752103835 813917711 326634792 656205755 816634883 709215351 803481870 366652765 64964176 567213225 230305006 530557514 106867562 718387626 6426312 444258625 764516967 559312214 295169921 763548125 975699003 933558889 976648756 935594711 285185746 538688123 499255323 706979970 242667412 609993006 27429779 786078843 12504241 268205394 741568562 186339705 266200007 546211801 879090825 383059449 63285…
Output: 831435323765

Example 2:

Input: 623 88857064 359464978 500463142 511052000 698532587 124850996 915047312 90108838 997703284 859582008 336499315 736691212 378425262 97043200 870877217 951355948 288953188 734629974 781003993 854718022 181153520 507440454 371908453 649814195 103423756 553725912 305623206 603783874 174162681 673666602 469419358 874945372 126428025 210247502 15745233 433760555 71674335 350555617 924680091 446371641 840981831 628897071 237228304 945010327 475737220 583242287 117471535 531057192 208977723 701225278 590170602 379745842 699150244 611878169 130754382 888940768 561457848 353797818 107786010 923323161 503845590 892909219 363920679 820151978 253391937 565257629 289265301 723913209 966969173 793762986 856314425 476702564 398315780 839921574 610559861 861755800 213947605 639579823 893339015 440107787 1…
Output: 293242985684

Example 3:

Input: 441 21002475 988711021 716820450 441212557 561281979 489257481 571717664 358294772 12560416 332126344 11706726 44485899 209348846 142411541 339317702 580548737 367765475 739568887 43782994 252741654 696392988 559364422 548356259 609937556 357421294 395076266 699073359 155808841 659530125 654947519 517875997 89984224 956142653 555113607 285145181 578745265 863264856 500779748 582726808 630422688 990140899 25981605 373129381 442064201 464055432 309433178 381649024 319612786 637788122 720709969 672025047 617666179 619711054 233356982 21221065 115522592 77196862 656880273 26535536 257162309 337676700 145851742 194890734 232351979 319294260 287982275 111283632 232139227 818821619 108992792 884076678 222163750 771281984 351898780 4870803 151381054 87266099 128479405 907806182 58313351 75491295 9…
Output: 219189187476

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Piper and the Whispering scrolls - MEDIUM Coding Problem | CodeTikki