CT60607

Cartwright and the Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Cartwright inherited the kiln at the tannery row of Leatherwick along with its curious bookkeeping system for ribbons. Time to make sense of it. 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 <= 2860; 0 <= a[i] <= 1000000.

Example 1:

Input: 745 493142 327200 712628 211403 305113 449998 694054 629404 353650 368090 107198 51452 366855 230483 396592 326693 486065 21892 50488 25445 848045 790514 521297 316445 536495 564571 995681 953403 712517 431145 845691 276472 447406 691119 648059 697291 744788 886627 725431 97841 508237 620662 683482 418761 363824 582648 937179 115982 105622 719190 601261 550860 593937 691538 45885 845932 296899 320528 585657 562875 796239 468224 570935 455019 858377 356691 946026 751984 318831 313625 759594 712281 344609 858587 625981 828221 121840 636259 668177 658703 223697 758905 484195 970945 257440 788511 933279 555115 254312 479184 100963 578124 455399 771354 166444 563053 609464 435781 37284 300316 631205 841277 840084 344252 813098 513744 300882 238722 635416 411933 842824 585705 115948 370562 11213…
Output: 346396074

Example 2:

Input: 2559 64007 455828 347506 990092 765165 152320 411230 48847 794245 468988 178960 18018 594264 997778 3957 587601 565824 79809 886758 655441 518494 977935 794109 107555 316174 25777 637916 363291 867632 867658 922166 210637 502698 905391 814344 415038 473122 822963 510167 213762 750129 773934 312161 619369 750682 263963 258017 394596 921536 468923 760783 529021 336808 35528 839220 311015 356923 138196 665285 495859 616769 276267 509079 588765 44097 915357 501323 309097 430337 657156 699727 440186 828100 463474 707848 459618 633065 897507 233231 905623 7293 877449 982880 298320 753971 682350 214619 217097 163711 616049 35214 235775 99760 958772 526923 167796 36967 641924 66516 863903 963874 820603 368049 107057 501495 623318 362891 260639 5249 660550 890039 434891 626716 396603 928071 400537 …
Output: 1261238801

Example 3:

Input: 120 801126 674580 264404 740063 582269 464231 41644 967345 973725 743293 334567 720254 653809 309333 353060 581714 898530 753792 841282 461442 20145 29133 495256 220269 982690 193630 341320 709789 691667 763713 267334 239311 159612 341290 985611 540983 530096 947546 145740 689495 908763 933624 848563 436060 573582 176769 814142 424403 489118 946431 155802 136389 948282 47200 983538 216362 459391 916497 613239 813922 695795 771468 79436 833447 724011 329899 719826 687494 617720 598306 412975 629822 889827 951397 475695 635658 173236 352761 183451 409276 612140 46163 801983 906962 611981 809948 73524 362953 893157 70783 523987 492833 196483 19809 381923 64284 993804 389577 331799 199849 120432 671841 723792 51408 729580 159773 324238 952448 429483 172975 718859 301955 927277 191579 115004 37…
Output: 53114935

Constraints:

1 <= n <= 2860; 0 <= a[i] <= 1000000.

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