CT61034

Galen and the Caramel segments

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Galen found an old ledger of segments in the chandlery attic at the jade shrine of Serpentis. 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 <= 1095; 0 <= a[i] <= 1000000000.

Example 1:

Input: 968 94114035 655493420 734477742 496162415 316979523 288655912 988512889 87652762 869850188 130134500 991819905 112094596 995056013 82468270 415448171 967120807 349170099 708986602 652956330 644919383 445953997 744272489 479721596 481991740 809960741 463200022 613492884 159610838 965791596 6138731 2900563 260603502 504797164 535306281 338347151 261101443 674411121 266215346 413011668 132902361 376006528 123970407 662035034 83303234 567438680 583916761 48352732 910209582 680384122 581138128 624215189 857531305 738206080 42795749 377221574 130333412 383458727 73074744 501468998 46443082 358228235 604521816 41024801 331638977 712315822 156268260 840794161 347100453 945612829 965644218 134861842 857097861 190072571 556666310 519651940 563451664 483675263 585354260 754902178 146079151 103357075…
Output: 477065689453

Example 2:

Input: 482 284544087 510412456 658742522 400462369 164955552 30409082 476626864 266740026 421980230 712797308 749331008 332415942 337308671 802128200 477005061 897628868 676567175 431274711 503919111 430848729 262588822 645742077 806228575 422480199 801286206 859180100 786582003 75041578 739792902 433660283 933362635 321134233 590016920 356102164 410471877 617914905 22378664 850383874 833806359 241351922 602781072 451262023 909477466 693263242 617373885 143421738 17547030 962976230 237967960 683317766 616761629 284241243 256303144 677797036 681861908 890564935 675730695 805827315 291617 778741939 9816013 294345752 208082268 131142127 12963452 216662485 654396889 491714680 123214558 773468230 730441893 528337099 995598957 927594157 84991287 983287646 121182166 447738301 836634447 617426643 6798760…
Output: 226145430878

Example 3:

Input: 994 989856708 463244112 209149287 728793279 264854902 179626214 90501995 946379647 698715225 463080308 433247937 328930899 213985191 97007360 236208545 282073777 728436738 290764939 937048306 213089302 253694201 504573787 734086968 292283120 706654907 661905057 289704973 719773992 241127378 37631549 159278284 391671190 914072105 129667195 549608124 454443845 216408963 389773678 291398505 422076624 214438608 114123471 639801912 122301909 678461608 890726688 123201862 102027846 373568391 501707449 516489737 395706096 126652737 835182722 625639055 81244753 311773313 829692833 153907336 81178670 530445647 23242235 766486657 952848492 617754807 158212810 140335938 911879653 348679573 611793000 561848369 449573784 865694840 6952138 634867222 423654009 969279099 812619192 745450444 544009710 3316…
Output: 484072255614

Constraints:

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

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