CT64976

The Rain Ledgers of the Topaz stretches

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Eklavya inherited the cooperage at the coastal hub of Tidewater along with its curious bookkeeping system for stretches. Time to make sense of it. 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 <= 1607; 0 <= a[i] <= 1000000.

Example 1:

Input: 91 63396 178473 448216 413568 103034 113980 817913 340405 473546 952777 927627 155691 400552 25177 404324 673193 967936 382755 689489 337900 975080 146835 340523 633703 534047 412260 843807 220068 894810 467960 142941 195454 536028 371233 670630 473106 307540 311169 342819 997377 224965 812726 307412 185296 910568 358955 406278 342217 211181 467690 407047 498789 327073 26964 632833 857451 362850 36683 846297 745468 493574 127966 320168 189715 608240 870496 804618 122281 637772 922450 145098 950779 534416 906946 210783 11310 773331 608611 244789 206283 275430 703282 536044 321080 879054 842635 293062 778003 417022 805572 203029
Output: 37329994

Example 2:

Input: 1478 799414 580621 40260 927046 269077 233273 829150 171649 356989 571393 915621 924173 99984 74206 955866 135927 537259 538984 932009 343080 133983 132149 580127 795542 254500 908842 888442 800031 708237 344553 289414 83934 538890 319932 675743 372133 50320 380497 550170 207374 543906 453724 766321 518161 464175 978058 88327 179998 498526 117670 483971 255579 648992 999 565925 40466 501976 274531 493030 302174 913752 181576 358374 741155 732440 543488 462921 186071 80350 646299 535149 560331 502713 633726 156511 446698 641000 318195 891891 23499 431450 829833 648165 483556 815367 456123 515958 145383 363077 771853 437426 557715 765557 765801 534813 164852 20066 9275 694712 485522 876796 135001 150671 290639 268630 93516 83924 500180 49001 131312 11229 777044 258207 66325 399976 472658 166…
Output: 726652144

Example 3:

Input: 1134 21189 565250 405459 761708 173229 568431 356417 79219 728768 794712 221342 101873 974223 800142 658121 396311 285169 451945 985415 394869 588484 847743 887350 853084 616903 30327 763917 3750 159895 68939 700572 284824 868811 813917 592483 355659 320465 846698 71276 353161 726780 788814 876135 859945 766685 290338 476132 2596 120299 174366 600055 287540 198378 273597 512025 431908 976809 64906 898834 651761 73918 609820 299799 686193 605032 584445 280650 222089 351233 260089 998031 36631 781755 220543 94387 664597 244297 544116 415678 282428 558248 971406 225852 622567 906724 310476 236993 843254 875132 961402 854766 891033 473370 559859 750817 709266 268249 214740 204088 413496 414214 528844 56271 967503 21067 318064 182720 79358 281974 307042 118433 76913 339462 574936 390493 785140 …
Output: 546355260

Constraints:

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

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