CT40718

Cartwright's Rain Ledgers Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the eel marshes of Slitherwick close for winter, Cartwright must finish the windows ledger - one figure at a time. 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 <= 1983; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1076 600962360 851967059 163026469 629709732 497411455 811689317 125466219 180953329 111833338 91980941 855766593 533850698 49898790 253475774 242107883 541041445 393255467 166124866 718032384 892151481 450295650 611917022 587937646 298148747 566662539 652185232 14157 871758903 680464380 675982651 347423138 873873762 850528291 643376577 507766875 205306935 85183614 916940101 367083878 876527172 961161079 731482615 640626080 763443439 658960678 159029222 35766127 713643742 854945554 487760549 345459339 427758066 307207308 120146471 807625941 694207454 907067275 103869062 61495307 709798213 421404181 460963170 816115001 961054240 85669038 593986363 458264174 702501438 679899609 906716472 707559621 766342636 931688124 970349464 725816065 332322913 717311504 447223869 5295095 488345965 6596839…
Output: 505687087434

Example 2:

Input: 879 481871405 830014029 430012655 907375588 694927785 617886502 662459091 521792903 977228129 656474476 129595330 740881477 376952872 129269280 126359428 645282200 787900365 745943777 51026653 243159380 829061896 949534771 848724459 971169559 684305705 435886869 543714205 484242195 575727671 618710573 456108034 787862635 244697894 906833118 817728087 862695674 720498716 549796679 749950491 476397330 414702151 336242954 813344090 251546998 517340789 224596421 744597579 21391570 651115473 934894055 390016807 817278835 896810541 892815622 639656421 130568100 405573905 732423873 861788053 445276348 230853643 337192652 871272652 156637809 820598225 59985233 110556498 402620149 917217513 602811937 346271942 205447444 291831154 315687746 483818242 394489639 914605150 260137621 589593891 302400080…
Output: 419124391516

Example 3:

Input: 1580 715993517 975552150 138101236 603230807 252157312 741649441 854893126 746885450 782893084 671024920 316506999 528078027 869817605 229989832 379870500 628875805 504115834 892605705 271938260 969085870 379628375 316417524 115505289 727530474 165370301 981063681 869192909 607325491 606741515 449795672 674894889 69221391 379109061 31517497 12152685 816233316 719104998 34355064 877561116 225389465 864870869 125166401 903306841 164130199 250280023 820662240 390281430 544318150 516494944 846368416 932266996 190626069 63992276 87136963 659156561 268011409 820059962 719492244 634228229 457047491 282399807 454090719 107033260 38123639 775405641 325845309 392053237 905682649 115351271 737474519 515392056 345557750 165277004 101812378 144636264 270338814 797463458 370183936 62846910 910562692 673…
Output: 787985634388

Constraints:

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

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