CT40218

The Rain Ledgers at Will-o-Wisp

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the fen lights of Will-o-Wisp opens only for a perfect tally of stretches. Dev 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 <= 3791; 0 <= a[i] <= 1000000.

Example 1:

Input: 835 844625 709200 728447 808202 284066 5328 589759 827967 282496 174894 755663 875637 726051 980628 301031 986337 858896 635232 745648 760724 848148 543968 204702 771209 146526 595792 471934 522897 261290 492511 77094 312062 633515 274295 647021 269207 552913 70508 116668 46761 244028 538968 122281 342063 616487 720547 858617 408576 536989 495901 684628 270540 121256 971316 689802 995979 264304 527652 609255 124530 591966 435156 277984 910906 374313 301821 12895 157064 485083 870024 11365 960773 25728 178502 359987 993154 571906 94731 479885 188873 163174 509713 315756 18710 212883 939332 196472 663414 48448 194597 733815 448512 306569 584487 485269 962822 536460 293684 775039 189212 233046 785675 943658 501718 2268 571057 951584 293380 855452 747457 87229 446408 842043 792493 772038 15991…
Output: 406980865

Example 2:

Input: 403 395255 201710 96058 499933 780851 952545 932598 976790 782203 818383 371523 421010 935976 516369 756754 299547 72019 256977 62955 822278 231488 239785 293751 244210 895350 567906 213710 547762 716835 681443 294223 945217 796695 880695 101943 736653 954696 460284 204397 696638 35511 501324 848420 53885 454122 644799 345296 81490 625965 713930 213998 404855 891864 747837 959901 634302 864799 377900 817393 430759 904566 508474 614370 882880 238042 693705 320029 949839 458965 424491 826481 345699 756278 393393 597438 695669 929858 704759 613342 262994 717348 850398 762508 790562 659437 52283 444115 553057 400404 364090 392722 978432 399450 847306 521605 99233 135184 461490 415913 56731 257397 157427 459828 823081 890046 310914 152801 475107 469392 519230 169949 943366 280818 977469 208405 …
Output: 186830047

Example 3:

Input: 588 115406 895904 907749 64114 358440 834282 50158 117364 194034 111968 75445 766591 316042 719203 922402 54711 210297 182322 88339 793095 426755 273998 873288 685981 36 734353 146117 809494 662205 722608 912934 443033 537616 387835 67081 550239 741633 197426 128905 663622 185660 685668 878475 468525 335833 907596 790135 261562 374636 721896 807984 273881 745253 39672 855024 202956 760986 789462 442179 692712 200779 655218 842794 202613 743448 546041 644660 642465 416201 589190 482729 428894 572230 713135 690525 271425 993034 464162 288512 840956 670546 348771 689324 194089 635430 713964 299311 234662 566310 73794 687911 762185 252718 377356 673608 697738 702560 45709 72973 677616 257389 701304 177745 473956 112944 175258 348312 766833 549757 660834 473112 58204 207 466531 214293 128355 54…
Output: 275533586

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Rain Ledgers at Will-o-Wisp - MEDIUM Coding Problem | CodeTikki