CT55218

The Rain Ledgers at Cinderline

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the railway depot of Cinderline with crates of windows, and Hans the accountant must account for every last one. 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 <= 2809; 0 <= a[i] <= 1000000000.

Example 1:

Input: 702 633215179 47176058 422215082 584210053 650284421 595626727 790184244 613271321 58124931 431850801 209320112 572796114 466228706 385417041 357869748 646228803 844293770 392209497 581216873 966106080 815637951 374445538 370561788 34984582 729346502 254098473 977163118 637193052 537257546 923622380 918647007 912127604 670585461 165337463 229337996 4887332 261973359 361355531 822686028 201540094 245754953 772371785 878378239 766105370 369753874 217797074 49164063 983680798 206969384 263231805 36471725 619921743 744410047 725623161 341116037 248572365 834135181 851554039 658628213 733597274 339939667 665583363 168583297 624343933 520904649 289446637 592955830 231951850 285584104 350569002 569478885 41900064 381644713 588346096 536087913 707753686 149954084 563544968 579539193 99649797 64169…
Output: 333914352056

Example 2:

Input: 1577 598348930 495400225 191095818 544365342 747275278 872495142 947170767 84826886 736326406 982444038 931207543 950297994 410393220 202097934 344103873 47312962 32402913 834570137 897804814 851143134 719755435 914297099 502833327 427510383 678251665 816254236 605524390 228095727 147749868 268185659 694363816 972417865 368074196 364805222 957259708 195050879 640004568 320558109 510603212 760500423 369167576 557997347 814510149 613996015 352477073 940291969 79207542 987842420 707455793 22811229 248814069 975494528 310364271 788386186 944945048 242039387 541802759 55495618 376522725 394257701 636117660 953113780 609020869 536180623 44465911 545876831 915668774 628058363 738346854 490968632 847468150 508924496 584445186 882614099 818329772 737635705 198856706 933591687 626895070 781287543 71…
Output: 766252293332

Example 3:

Input: 904 274776783 232895708 314776924 42213118 925691593 557280157 727266358 721634641 101946177 506187428 469242956 526714572 106301704 91980560 635465017 644684117 986069094 417501472 82032457 783097128 776697131 439218408 668218793 504625148 382814642 104813773 632710998 271800722 812820937 862261321 414505980 992826693 834146774 61947990 742665370 644082144 411180905 152789629 441321518 549869072 696199015 957470014 205361141 159972471 914910800 970950094 878849390 682211223 341735087 931921538 691475146 825076316 134517500 44325733 788087159 949132189 455889097 15800826 284382060 257309432 5915353 544502338 823394639 456793174 24344880 828274681 379954956 555365236 135310169 692334205 642289486 189440453 801450368 881419367 561027712 45260369 305146863 812130856 878127176 10722180 7532183…
Output: 439795074678

Constraints:

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

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