CT36256

The Rain Ledgers at Brimstone

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Kavya found an old ledger of stretches in the kiln attic at the sulphur springs of Brimstone. The margin notes pose a precise question. 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 <= 1380; 0 <= a[i] <= 1000000.

Example 1:

Input: 1044 455602 98032 358292 535379 359136 55813 419189 308985 530186 903972 999742 675130 214669 801998 402683 996822 719701 955015 543284 704925 865838 376893 923984 312858 594340 868888 302947 51334 693007 795020 207749 159790 739481 337000 950 1420 160147 270384 735931 584091 957598 270979 212761 312146 772842 607874 348217 45197 548603 993026 792574 43890 544262 751023 340885 859101 282416 922098 954786 668138 978330 481754 522140 851297 89732 223450 364454 411991 325992 904136 447768 106238 861427 270879 757957 310481 802451 300118 893451 820901 489095 751611 276821 436846 906973 35135 726503 756302 935674 756219 460030 653608 516520 404456 405495 653014 171595 786634 153716 59405 263614 668541 66463 788341 938165 438517 614323 120657 137653 755959 224404 103471 762638 1827 802626 145249…
Output: 519432735

Example 2:

Input: 869 655526 825501 571696 681065 932318 351658 91449 358187 12310 597940 921432 90882 842110 602874 10991 408377 778298 512406 246657 560043 457969 817402 616624 259176 449001 770747 954610 279656 434877 545227 152182 517214 662399 550527 414287 793687 473144 903238 15714 4766 60106 266342 228522 631691 746256 735361 395268 692458 827143 205941 344337 746160 251723 774275 87755 726262 315353 339367 665874 238497 949845 105894 764160 9348 674181 454172 34616 290055 592918 745700 590099 24316 131200 409554 304669 337774 906979 888763 10973 18592 215142 601307 603422 26814 622187 644277 598168 929689 582641 669778 441467 794736 283729 57278 438609 560391 34378 51923 482812 399144 800136 709238 624080 573114 664421 233702 299661 55277 799813 583927 636633 615296 558441 634471 465839 397470 6457…
Output: 421020929

Example 3:

Input: 509 582002 405482 277268 903252 819448 719051 655210 704676 438907 25911 197624 352299 719184 430115 794974 972635 196315 985766 659852 64227 806436 285822 617467 184324 870718 700095 713512 87905 752391 797936 997544 714272 465746 831664 79638 205247 629287 126580 465680 513660 21008 767761 677631 675567 832885 599343 713226 587033 806785 310517 951199 424269 632581 700158 76376 101063 10583 546853 780872 50269 520099 352643 676668 134366 423129 529719 22093 457059 652818 467502 360988 19771 66748 330057 222701 117461 419449 15633 518207 16325 349635 817815 226263 819034 881994 535783 827075 336218 427763 364980 89859 405527 470545 276645 435372 990289 940374 453534 403863 58942 317319 708658 491852 339676 23378 269189 641790 355140 508781 976988 881947 983427 347546 368248 53399 510779 2…
Output: 248497464

Constraints:

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

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