CT61113

Lothar's Crimson windows

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Lothar the measurer watches over the ivy courts of Vineward's stores of windows. 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 <= 2987; 0 <= a[i] <= 1000000.

Example 1:

Input: 1765 883359 866302 936261 933986 859955 643176 280876 421000 404024 213153 141277 657125 473152 222343 486225 788802 733717 98598 907399 42114 352502 638185 626502 762712 501319 513191 282218 452073 510688 107935 607182 327611 543939 954684 779711 702165 601415 633131 123029 963377 476343 832287 5689 790276 465741 270565 970429 155058 852164 611251 394229 832723 260072 203184 97611 280882 664974 136268 808897 172678 70831 177274 414060 168491 103714 200259 557742 454183 539073 704499 564250 128249 537504 543011 837405 203767 562539 683257 112926 561289 542511 503765 436268 146724 680113 111486 242732 945907 145285 676875 766318 706394 633262 793804 365021 540732 364680 7472 26005 993176 724117 347701 605861 345765 188383 579488 72129 365686 774947 281235 4455 128334 261254 907042 918477 85…
Output: 849811668

Example 2:

Input: 1354 686222 90155 58797 901998 49351 168554 394041 592098 749046 466478 664027 175339 240461 336375 830932 489008 97201 237882 775481 585377 68904 902649 789044 47404 952113 892791 373031 792174 487164 845227 635330 403669 279600 329231 990767 816858 170366 207149 117612 140881 945037 435331 11052 317546 278796 171223 667917 464045 952771 498579 313785 789354 74003 363099 475977 153145 19720 272758 666931 971558 421236 785891 517765 387983 852811 877359 672904 299109 500957 173590 305992 547295 662399 357995 314720 167717 612806 577701 998887 990026 224761 642334 669122 1961 665698 36647 619449 151263 14379 896078 440807 439626 315736 692968 723569 604884 275074 658559 804363 975146 706546 839697 170806 183135 301281 192453 520710 734469 659469 462194 804058 323445 813051 394185 507094 279…
Output: 652386852

Example 3:

Input: 574 187282 538405 734239 552929 657106 96912 851607 189619 555567 994513 664866 344668 475248 128762 545637 682481 981838 679923 767113 350636 212823 151387 77358 496762 965967 171203 320358 889902 770153 391285 251419 535703 610790 940712 715043 57538 860307 864894 607807 673034 800276 576457 394867 992676 270533 510634 662662 306122 985256 252635 21866 442690 967234 827621 917287 324674 393553 50868 2694 930070 648772 480039 57148 321842 140433 66422 610357 428929 726753 223414 655592 3100 465541 104182 854684 303825 696340 216510 575226 839481 399418 824285 873990 393516 109819 945685 207094 77491 674314 511382 353657 842298 835635 467183 147414 673804 378058 968291 623434 433053 538094 68802 487803 333142 541925 346402 264640 467484 956464 852027 415719 887509 475419 384517 335301 9799…
Output: 277663743

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lothar's Crimson windows - MEDIUM Coding Problem | CodeTikki