CT60979

Odin's windows Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The chronicler Odin has been asked to map a faster supply route. On the desk lies a long table of windows readings. 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 <= 2016; 0 <= a[i] <= 1000000.

Example 1:

Input: 516 911221 723691 460409 644062 973320 907514 850549 803121 950082 504732 57251 406900 996577 88245 597213 101174 544347 98399 468310 156442 138954 843825 116933 381910 904735 441075 135553 133300 639519 402526 462121 852191 685472 328357 884781 781454 947104 330130 278321 992042 116344 923604 954251 655242 6221 515220 182552 964998 468351 77398 753977 275520 320211 832004 858839 495873 635284 880418 917941 126142 766583 768795 26782 602112 793220 376713 447788 897393 445741 934672 411481 720399 171269 226973 176766 288819 261564 963509 362112 727551 739556 37613 262883 297250 359625 217483 653081 939657 308277 959806 811458 745615 320290 61375 359450 581251 36849 218469 996438 435796 811219 695998 430489 492749 195238 130373 505539 608360 777137 701279 627802 155167 769078 617812 47759 86…
Output: 255719420

Example 2:

Input: 191 214226 173331 774947 464583 46736 217950 151271 880897 902401 187566 874476 382784 552712 731052 303145 774875 70438 731699 46622 14820 383396 416633 78713 568879 198911 215463 604806 748035 608230 587979 682021 62649 506862 107089 303060 43847 251866 794671 435802 52425 294553 333961 578565 275189 696665 529706 621632 14395 782524 674652 118309 512078 831190 648441 171117 323934 541800 50913 763157 435915 606724 842425 454910 25067 595942 160641 507149 920314 858947 610813 873160 746179 937609 18975 614687 43237 473970 975932 750388 139927 960140 213243 893521 372247 824992 337413 598720 346270 163983 782965 33475 72854 950222 352045 569450 74030 961628 37176 267274 18356 423647 513315 26731 525847 410706 758821 303552 97097 255028 466212 649698 65803 892945 23062 34595 232097 653281 …
Output: 90499663

Example 3:

Input: 464 903824 499039 505375 841995 20978 611008 160787 730719 370886 113605 695390 577710 586642 148810 379668 435195 942085 149307 838010 711706 944655 281849 111186 149574 689360 235143 687406 125049 182186 567151 646862 692106 924759 749866 697925 298427 196639 705532 672600 893120 709431 453227 835789 835043 225818 735807 663005 755425 387817 853958 510551 134415 471216 983274 320472 576957 117934 101361 955244 203296 698052 763513 412051 518186 252275 403892 695955 712433 754979 900842 676613 243785 234224 785868 539000 577771 428259 501663 676516 105483 883850 676773 842187 40141 17974 976180 272926 932562 73021 299263 527013 388836 917915 698589 836033 856449 47320 558057 576702 754862 26988 858437 211852 840578 7613 753114 510659 412456 558638 468951 116163 299471 50564 554205 671132 …
Output: 220277877

Constraints:

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

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