CT50706

The Rain Ledgers of Longlegs

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Kian runs the tannery at the heron rookery of Longlegs. Today the books show a list of panels, 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 <= 2422; 0 <= a[i] <= 1000000.

Example 1:

Input: 2278 997298 856037 981520 452746 419003 87251 708684 53131 234702 359833 5573 831492 497670 385261 165145 73886 424900 851221 102832 505696 573708 760046 471781 737854 187217 401981 906281 330065 496061 915653 49139 358746 742596 432338 560625 684314 692267 705688 366 75517 383888 791978 966570 623501 509086 394935 511356 692033 29414 586364 908238 678541 863824 254784 874248 366862 936226 450243 533016 428754 110055 321118 233353 175477 312866 117483 278677 727105 177005 88724 965286 174363 741427 952059 566186 787351 520246 464652 303270 919777 805610 181722 80547 597850 762723 371254 998937 583640 373737 867350 587993 495153 657916 953016 787952 255624 820260 512850 534683 932637 932389 76079 287411 221621 817101 462524 556713 801238 998147 577699 398632 790116 544029 487046 439841 1523…
Output: 1111396103

Example 2:

Input: 1733 50727 869795 387284 241036 457554 287535 568507 700250 256774 921595 591848 151523 973518 904109 799350 488270 356911 522393 9521 960343 387674 758159 565475 389770 153107 392731 933133 337297 912467 847103 598701 129773 566614 573768 157416 393256 827713 85586 370485 638618 434720 57852 52237 907696 145345 116248 848011 810043 375831 459878 708695 265896 312127 109955 109539 16858 304297 826157 187691 170085 252394 309778 678951 789268 543048 521529 222121 870521 409459 117625 98286 583807 737917 159012 36778 34498 553358 164099 190044 759473 551839 620630 297416 380581 207559 81797 684365 744955 185284 300931 316937 335274 861472 17450 263094 246690 855051 109542 638765 985740 82431 318491 285780 692765 626207 126888 463070 967419 521956 563576 383696 923682 656891 467935 150941 761…
Output: 857073304

Example 3:

Input: 54 860174 81825 102811 208737 647210 597341 493788 94413 485362 613895 282475 876767 392082 837458 198073 726401 620608 355492 783734 311845 44065 135067 10790 297075 221449 791776 906553 763089 113554 430945 387300 407761 747486 774869 257951 509528 328377 676188 950884 433964 970092 994923 292028 557252 867806 289486 982734 531971 303591 892058 292072 553386 551829 767127
Output: 20411673

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rain Ledgers of Longlegs - MEDIUM Coding Problem | CodeTikki