CT38370

Quin's Rain Ledgers Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Quin runs the counting house at the temple city of Sunspire. Today the books show a list of segments, and the numbers must be worked out before sundown. 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 <= 1954; 0 <= a[i] <= 1000000000.

Example 1:

Input: 38 593623219 520465901 700173418 232412268 352488232 89931990 225757999 733107131 453253267 961191662 135150455 829620216 843125714 147873793 542738474 577295222 471321517 117735756 510777818 65044847 940677144 389840205 405648453 698346464 917433378 494100298 160840610 859428205 170066614 503667620 89904192 54909587 539981998 917887271 963940513 172272645 625989499 353053169
Output: 14392015256

Example 2:

Input: 918 627034882 805601368 152931997 592046599 968279695 29369726 287778442 645065573 989979318 793668388 999111539 508961868 711698336 88058064 514048430 62127887 968211159 589424907 35159987 646919431 892743151 633366656 887256676 651243538 226199001 682869451 183169572 161492649 486227481 974473664 964223999 405893419 253302402 955702640 578402949 704340989 395651300 517769366 591240270 756240086 142771394 84460903 818184335 191908652 877346599 219927706 249894629 208011236 296342402 866510411 845469886 318753321 971514739 570090388 973459716 610453597 597733004 851296121 469226893 692092341 307439391 213570626 874381258 458528263 369691710 8588174 191981332 612336496 442060413 770965086 387783670 603875463 161829858 711010541 125886578 204212043 886039839 316756894 787120816 337309486 492…
Output: 439360982058

Example 3:

Input: 797 874277229 982431639 621771951 719454826 323151281 438678072 117336698 57863878 818311942 700466098 940249136 642789064 870130203 372480159 528307781 205201434 150239173 672829238 422537687 917353741 350459337 887096820 119076333 827683779 916350772 251107406 761207664 451714011 867814199 754439670 534919537 437505928 403412435 243008070 217573406 822333322 713726858 325937932 168350570 896992457 39745949 625570060 44189474 339681692 366288105 795643327 796633236 900992300 721724020 991577226 367647423 521397610 591107896 784574612 598872270 886795670 384019821 783806619 354066002 132704343 211680889 11533837 383489309 883662693 127044372 524136523 82590304 964504295 24707187 70219848 374981677 145504174 462445693 309697934 70241653 400121573 392164957 275354301 288133931 440922078 2362…
Output: 395393602300

Constraints:

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

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