CT58600

The Marigold Row Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the saffron fields of Marigold Row opens only for a perfect tally of scrolls. Diya 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 <= 1707; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1471 924038082 208406216 936236106 400322727 197856321 492113602 459791914 765366968 792445518 273780282 310424894 810120401 628931891 119534440 609682757 482674248 554085333 352310142 429445885 496724603 6073898 797060445 189384827 538658039 255466251 844395675 639176553 902348601 114575722 698083436 164097911 557830185 218826124 403007478 592384348 70140407 554882425 850034540 493719133 428266793 67745864 16734753 340100375 609747381 781281758 708368709 737890610 324019143 676902811 414219219 305189590 460360282 684035866 617854470 714208729 362072164 301605406 430108385 147365610 587221345 258117711 804014366 908721169 869129065 854565800 903224477 885470127 365416753 761739355 755115118 417289750 653478985 281906781 247910009 890933181 577442267 961970127 33495007 315276216 209879339 1…
Output: 700289842279

Example 2:

Input: 1424 48611932 424180835 995841626 498199248 877514720 238773295 6934256 16308101 25433722 865874426 284426000 616684961 427070253 831206188 936483209 726792823 38520534 561780068 467476699 197442062 244958580 641438210 830987750 38242264 433120352 747216488 780130856 426192710 516664273 171378830 711888075 334435799 372887900 87367856 681802816 654528208 971852428 472038777 443108922 210722700 126580814 935531976 136114558 989979104 176438451 660315134 317174305 358638192 42404118 950089304 877224448 253459197 714672523 361967918 439953697 39746970 67319362 469886871 488155126 525111761 209793132 196862668 795012058 775013476 159240204 140424934 656924157 139606893 12613456 105528857 638749998 708216863 556308132 852540035 388124832 179777268 903692478 49577090 192205476 565701056 25050833…
Output: 710283044187

Example 3:

Input: 1089 102694714 318732554 249476596 293452656 845782541 409706172 288708217 233616608 950387624 479790596 578863933 825877565 395084914 303518091 619175512 868109115 594542032 346162412 368292521 63524454 891519383 938599572 60807619 295435793 309586326 448876858 593394068 798878552 489414321 518555489 299793357 783372675 940177916 694312288 740974417 310615418 408211690 21579926 561048274 853496735 99069131 798699983 938547801 876758856 418028902 223860108 423470365 935689224 469102383 281344924 360109877 567678810 529951751 913665290 633497265 439654816 806030017 828657539 691463148 237168391 965121669 630605065 944914823 318120089 122123456 578007442 340505404 92631127 326124270 342797250 730249943 437031558 207606524 101251457 180365809 512540394 552829201 660256746 364188941 392148052 …
Output: 529903664845

Constraints:

1 <= n <= 1707; 0 <= a[i] <= 1000000000.

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