CT61918

Chaplain's Gilded Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the tundra station of Whitesnow. Chaplain spreads the ribbons 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 <= 2557; 0 <= a[i] <= 1000000000.

Example 1:

Input: 615 750951722 848384894 830794310 886532944 117347078 486241051 526574288 213366264 669633211 109485011 363363922 214334960 558331530 944199 625258635 385128839 610707439 623201081 244569063 618313055 873232116 848326835 21909705 238035430 438475652 639609439 338634551 196004131 601534594 199620739 884915594 15160072 22745037 713651456 689651063 11229121 360127727 875576030 777030137 696468252 492334032 575833011 903943957 92903711 615179438 370356977 295813600 100093868 60860192 167047876 362633556 386408904 793139447 574872917 804570525 390053627 695500573 772825080 479647875 622266654 32380990 536011547 487886299 356417665 928023945 342422412 881979299 792123324 882624711 896141285 133980411 956728479 552497611 914857205 127297316 948139652 87498912 234579195 944451587 165575929 4935182…
Output: 290939389034

Example 2:

Input: 1415 661693439 751928155 392331357 210419724 217079336 893332633 394084983 860231049 590172794 468757595 392565341 696728164 324573465 7019562 702210441 600340470 545428073 754044256 133026144 740521400 403317997 783617768 553764520 864466830 467947544 213476460 451689491 757727079 357875457 447061656 226807227 288216704 448018691 242864038 912805945 588358020 8517079 582673703 444659712 92603682 965948681 134273910 545681415 316192244 355848967 348318520 229032045 321729390 430158694 604135509 14314114 46700868 882523167 481811376 25230280 36765861 972684439 783834880 68862274 95231304 905502420 520855738 351974555 897206428 258119575 352789410 972723933 848005799 398605006 832328224 765749559 255402622 80875078 390838939 644571789 132716724 786839623 113963596 468901324 64734468 94615846…
Output: 686319190802

Example 3:

Input: 1546 843008374 99326096 784592239 350990763 331740545 714260588 903930498 571455315 254506603 934727799 556033629 165912719 63163676 767695365 147478659 337572260 280264143 993096501 468463642 225428153 447608073 602697592 878331874 658569103 844996451 267347047 628579286 589459455 211344038 225101299 959486686 221972507 999418099 500801859 212902030 144021557 348318429 880668757 492988454 804678348 80168764 206434133 444273036 373412527 232357343 596304418 455162297 566344444 400075820 998725397 866619380 875771021 550620894 101199857 84924322 923548791 489825452 593171677 36521620 81254900 454743637 683171514 144042257 739788027 151461051 493063813 471254431 541394210 936367882 517063175 703678680 587597145 660223717 65615805 622672035 837308413 741259202 30631374 843041669 965217488 110…
Output: 778251076271

Constraints:

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

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