CT58520

The Vermilion Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The bookkeeper Koda has been asked to forecast next month's demand. On the desk lies a long table of segments readings. 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 <= 1745; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1446 843068119 439018118 32607619 542414693 93520284 598473957 714901149 269306431 419284082 558937165 84038777 536716704 886483728 587829547 979999742 390942070 769096719 934498409 174971730 820881846 398072365 376478322 261576544 773535712 655444175 729423153 149197353 746432035 520955142 603712978 362878123 335578159 954368836 606626462 770240759 283915765 585762575 46367022 858536257 150943975 589231564 147164256 496952367 299682286 257597223 695279287 476096903 330785759 867084357 65274686 919967390 709623159 704616980 445001135 986174989 295086536 828419194 325707014 179825059 981454300 62280380 893604012 397890555 656493481 335904241 941281174 354522918 326587627 426633781 959230452 348287385 965230716 308833817 485540432 1779822 309481929 833428077 991712577 490632793 835905162 675…
Output: 722757419972

Example 2:

Input: 769 476883980 867489261 986652675 623693133 495546719 490465942 558919654 904159105 430848992 669630260 749759970 787240892 599440667 56376563 31522235 436549429 118741254 928751943 622068782 367927013 415117756 636159719 371506202 480871947 981286011 665698012 696909175 263247560 755052655 428323560 878610317 928944251 633614062 75562588 417383288 462541434 937463923 164933289 414809114 90190300 335681814 423518868 215891475 32615991 34596421 413378388 55719958 782513101 157551815 28331501 838889668 891548538 866390079 553985251 666190388 938531131 115135534 684944881 945374218 609748533 513830511 205212430 558478309 744344865 533309141 954819546 416103874 235287412 411321585 577700890 264600531 860510358 239026816 787163694 224540447 576631565 434289727 261808652 711363783 613616149 4534…
Output: 374052511014

Example 3:

Input: 473 565763246 983371244 359891957 66302696 259401233 65486304 100458557 804813356 63948536 281928541 226926402 290755807 53632319 418752171 213606405 915943367 648873255 746245325 29966552 952471393 697711922 15467604 933499468 157599076 391298404 575249396 487959031 608694909 20653138 504693536 108831937 332669826 223746271 759133725 289547319 222899694 618565940 88584623 357069846 476143435 136313984 562769628 80222246 271552150 505148458 699559326 862402787 62813816 684609220 574309368 615940684 947550816 302108977 996544732 917084116 356219017 876662662 77934925 956934174 492708105 330077523 900667903 334192799 611709327 911211082 440245316 532949807 41046283 810253058 551779345 365955947 260263729 5660937 151420928 820388086 239140929 502646589 889549295 200429390 398989379 301396616 …
Output: 239545239990

Constraints:

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

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