CT43246

The Rain Ledgers of the Wistful stretches

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Omkar runs the dairy at the granite steps of Stonehallow. Today the books show a list of stretches, 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 <= 3081; 0 <= a[i] <= 1000000.

Example 1:

Input: 1274 58455 400184 341139 890359 723216 295110 821131 448677 551013 849096 685940 762796 830450 354392 868216 23367 386209 630620 120839 863448 117542 293217 42590 569060 934073 759685 201917 704211 686301 219389 505780 867950 84511 160317 887991 416328 408688 991304 264946 597742 293644 172333 378805 920191 642427 88166 985348 156129 396618 260052 956460 62029 405951 104217 652354 51213 595552 547713 398871 248348 3466 843001 528438 821629 26309 363407 867529 770845 120118 77591 938120 781384 600543 656935 691933 132760 536624 965715 392131 178614 443764 415612 683743 650413 248323 496014 957603 467134 505074 23773 947085 347611 557600 421838 128483 995223 68272 830082 358277 420540 974825 83859 180330 738043 189419 722354 815791 574181 305404 788711 486631 213975 165814 938431 982975 3483…
Output: 630785532

Example 2:

Input: 2115 726570 442005 402558 711175 987498 870374 7287 897769 824660 17960 109827 864997 556707 152909 437312 514665 475857 13179 434938 851983 965083 690087 321395 820065 374188 322104 173129 303385 357797 7245 142835 738097 14853 537687 57753 505211 905569 545352 698784 743778 370335 200547 294980 286174 834191 828651 502557 54902 356556 949300 258431 528362 805334 498925 977592 710016 509477 689802 562773 117011 804055 75948 684926 786261 570086 970296 170719 109537 340823 748891 604034 10643 648998 515946 455806 712502 957361 537892 772525 103771 632958 319648 719684 100551 675152 668681 719829 196710 617628 667816 59063 343716 529244 599213 429190 446172 13954 861050 407776 191837 634765 104922 455330 918035 889306 268083 222160 802484 874206 575394 645748 620631 909289 281060 718200 454…
Output: 1020137076

Example 3:

Input: 2094 875075 758253 711690 558872 723446 45862 116511 222476 176058 214186 801530 952734 351165 146169 419598 569839 475535 91151 24317 990254 783633 106677 738496 943714 663871 3059 576018 12430 211161 129574 120761 885861 229694 897155 407728 540859 691452 623680 41196 214880 595675 321456 895492 740196 17172 216917 269662 257728 409037 828516 224770 614145 539095 382739 208644 202400 937139 615148 810133 234662 408652 976805 261232 571770 432023 98027 697654 256864 178158 816254 624303 709122 334865 584863 642768 143905 802054 941181 159160 361760 360548 923554 40 659070 471513 845220 724154 46370 279282 527914 567680 380261 784460 661079 652229 87835 478500 39203 940309 564105 360525 392212 350648 152570 943123 408324 411173 225461 872086 159173 32088 839849 866783 91138 623896 900228 2…
Output: 1026910170

Constraints:

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

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