CT63460

The Tempest stretches of Kael

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the windmill fields of Gusthaven. Kael spreads the stretches records across the table and picks up a sharp pencil. 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 <= 2716; 0 <= a[i] <= 1000000000.

Example 1:

Input: 647 813831214 438607875 323058802 225050767 298435951 179851529 792138249 603878934 901688032 335886674 887003459 182736688 839936626 683535363 774900281 503041153 841445048 742562473 889145131 953152131 437630644 119132129 287032072 285995457 102889344 185244824 811382057 75508494 69070441 701223642 234148172 738399876 757018450 778915083 657612236 413011237 837101415 144541612 33380845 463339872 919594345 611414223 31153033 562226167 37085731 26647755 302847061 788316791 925246250 263899327 722242029 181859696 817917305 486679958 592897163 774261628 303051283 155120030 258958681 949407150 992732506 649946652 277569511 374121929 252282977 978464497 224726021 217511217 713891046 171273214 788236472 290051473 699147612 306193706 170563771 180306948 741992073 810531799 603607968 333673303 46…
Output: 315561980139

Example 2:

Input: 2481 318685515 525793144 865520686 36094682 455757666 132080215 383272979 34863708 562673943 278859843 337193156 562896474 829521247 529473327 308541741 927519133 805379903 602785587 831702602 536267955 245875924 760404782 788901136 104746174 239496172 741689254 41708468 988554787 699519645 562292530 249756543 822437090 315327018 63399959 494346648 922153029 530606366 961416609 566682191 399838458 38689540 723402184 301618399 430272124 999408392 884554981 190269226 27080313 270775679 541521069 673954420 165237919 288367962 666893853 931971662 231390018 767147941 793576817 187531311 132557348 230207503 175116361 899216649 764496504 137685364 421994892 347065713 228501849 712535422 449029024 924139551 55736297 459062660 675392329 9086740 682792216 511362412 323525242 21386125 57863188 435960…
Output: 1222861733688

Example 3:

Input: 2094 879330032 456536048 719112218 369920831 413026190 957447726 513599509 868206947 897636811 909017107 215851350 186266601 653258728 508202006 992215021 423063695 687526360 6036484 763789512 328223125 913328477 819615766 795575136 961814999 94727783 236519276 758298097 805940622 788226067 651429098 634636602 571153291 626935228 844840700 625289764 12754007 133847598 876356902 875837222 894532373 401344561 503665702 529171658 154092944 239683722 762363762 38590247 473534370 350794330 408530119 845837923 224231214 611618604 845585481 690994844 184649579 830169291 850618445 227125028 349866368 753957796 968662346 304593753 732234918 838163879 527060418 811700074 643950983 782935812 931367253 377128233 778687169 139057804 424539583 37355345 14886954 405392176 176946242 522443880 315332959 96…
Output: 1062164592209

Constraints:

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

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