CT57583

The ribbons Rain Ledgers Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Envoy the dispatch writer watches over the frontier camp of Duskwood's stores of ribbons. A careful computation stands between order and chaos. 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 <= 2256; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1480 317130763 869930335 6777995 169600236 470984522 207907330 768712374 818693449 879639302 397057402 204035941 537378118 146365366 609997122 652443226 62299317 791610763 851458105 348715812 720981235 594252502 747321450 817767559 460361861 179892906 440058468 898115315 301540865 764720855 355163267 635680376 178553528 669260120 809368213 452249308 840922377 24499924 170455263 59870685 512821008 520996326 893260415 336086334 164329696 441122376 52746003 737927043 261636328 548632145 993092481 687869701 406861488 183160682 183977707 717897945 617844448 869243467 579524198 114434402 7656019 27770132 869830538 744646183 326446046 951437858 109942806 546190177 291131717 2123204 744316482 666134463 433516335 47784243 437937814 223382664 762474359 54434371 424882442 339554087 990691691 36847651…
Output: 741168433189

Example 2:

Input: 2169 641904493 456177453 224582270 128184297 694358351 411485516 771261708 575959969 570959565 114112543 276557032 758213105 117151760 323157865 376364742 978939783 377339208 881938621 217871072 634157167 73561549 6665884 987733122 330727272 756720124 5103519 937991831 875320749 813636207 895068526 400949553 464554947 108002210 773269914 162985969 10004270 991447512 395701686 352959976 45306293 943516984 648865449 296794528 823423524 219750915 500092033 710166966 539263109 968622739 935484562 939750770 426678504 657317239 244918632 585120480 971183511 376645770 842690276 624945204 407976658 443995355 32382461 174463844 253913342 319589706 863328351 960026584 536189278 411874430 980792116 991189919 947858043 206253592 536378051 290722967 211373419 363171104 856367919 448024980 612131550 830…
Output: 1073161612364

Example 3:

Input: 2244 486341688 375062029 378835638 905788921 240875203 775910648 34965126 421370436 929776328 77369691 325107153 127961164 659200545 385018233 318663702 612290261 398169733 89156543 442610795 747016624 973012092 746588668 463781925 114355714 624625141 704300254 765241681 698862639 492189535 514767557 993134687 981154834 435531904 704012266 633900034 414407954 929795453 306864383 324000058 777342708 191565912 155733018 519094567 773631886 700862415 33030588 180656180 22476865 149975537 167734388 893191248 426391719 218978542 19455290 257218187 936166196 80512335 877939390 816668555 703479440 733421958 377891974 872079777 553134179 408539796 322009014 602221295 875011744 499637461 668125636 878132463 351681055 570163554 289624360 189161778 469800284 686890047 500187029 339430071 490228646 29…
Output: 1104574621742

Constraints:

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

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