CT63996

Last scrolls of Wasim

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wasim the registry keeper watches over the cliffside roost of Stormrest's stores of scrolls. 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 <= 1995; 0 <= a[i] <= 1000000.

Example 1:

Input: 381 898366 65702 265513 707997 856416 482752 139481 438095 198849 660727 195852 141925 528135 720894 816131 355315 270086 882953 920869 117528 173781 908569 227471 4094 926762 475995 998036 453867 311976 661354 800645 503963 613749 505445 875763 711814 576736 389128 403064 637110 594527 749526 25423 331482 855360 340773 405817 754900 976442 377186 771193 808873 963323 813788 968210 51945 892253 971972 816073 694202 758369 269076 906392 525459 253197 250224 364206 655980 968076 552733 51248 250901 579082 990877 173191 909234 326661 28386 695341 447171 329988 379833 694447 580419 728556 261486 294778 848702 347061 676050 538633 256939 82087 884211 669009 322329 664161 709842 31802 839575 882499 440636 324385 372918 142726 911915 637883 376051 600734 823621 33406 472366 39398 79553 462884 930…
Output: 172671551

Example 2:

Input: 385 460723 837014 763223 949135 819058 337880 279373 678040 39397 300750 56836 657820 685994 76251 187224 803403 769961 607362 385869 700575 822290 605622 937579 232592 454533 932674 337475 291109 1206 840253 382481 802088 303844 13421 483486 461677 298151 587844 463261 260733 796331 230215 887376 390076 40265 855345 291763 240204 104162 616000 321977 685632 415640 333308 993789 592759 927689 94125 15542 279218 68242 592953 163009 589506 593599 530162 348271 423609 879728 406873 252544 635570 788832 364419 44005 80618 118592 895795 785865 470439 375498 172697 628472 227499 406149 348372 671220 177099 21543 199377 606996 380108 275206 127310 11607 948692 91463 244214 615121 733406 878763 170450 843831 105152 429557 643824 347120 245586 44860 574391 543943 136517 250189 812503 665512 666258 …
Output: 172349665

Example 3:

Input: 1944 182799 481636 135485 951849 687418 214650 272207 636331 967975 495066 868529 427390 596702 658652 932516 38754 377828 235920 133028 774523 271606 253357 510361 795442 241953 910860 581000 925675 198198 643313 475575 521973 756416 539675 107932 459060 354088 918385 658018 549541 594936 354519 715382 695881 117618 928581 342625 436969 541197 295105 26817 48146 941848 586997 126631 428734 996495 878092 756102 356950 916441 74664 958066 218994 362107 936774 956333 242664 350043 139669 887269 453126 833656 360136 722327 717228 796090 642545 297833 603442 907956 279734 922263 996855 178257 840366 667442 528661 284233 392127 508543 723677 352313 516664 653369 433723 49137 152969 356518 344870 765159 901203 988354 290864 145205 374578 581715 913801 774831 156361 281582 269770 73503 35930 6379…
Output: 971042261

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last scrolls of Wasim - MEDIUM Coding Problem | CodeTikki