CT57524

The Rain Ledgers Beneath Verdantstep

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the bamboo terraces of Verdantstep, someone must optimize the storeroom layout. This year the task falls to Odin, armed only with the scrolls register. 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 <= 2082; 0 <= a[i] <= 1000000000.

Example 1:

Input: 985 311482691 699185613 786958037 216703759 464673500 239127168 331232798 872766602 462575728 670859150 932250020 42855172 810029959 859199895 583655344 945718206 145760911 335947749 834118829 983017208 232652834 364160548 428348636 993577778 875122362 389607952 22824158 859225284 404669343 495809073 462620275 312548609 584223585 127639012 100696199 462570776 679695725 112843356 115127806 643478751 592206084 644632703 93219529 776059535 9771790 261064553 580292363 836401718 651494731 191206201 276079406 885358644 131531601 588509475 158679138 468433434 821588145 836578342 881687413 481427910 216766374 847400307 559661062 922388964 288003859 93628241 255217109 14372974 786172912 873383573 152285524 670167647 992876131 100086980 865439474 689411822 584543384 530229954 716443580 397677367 533…
Output: 487631648266

Example 2:

Input: 760 184312038 39430514 680760722 443437149 520630647 594723428 153874104 399792559 278121513 328193859 374148733 989610462 194326185 148856805 6965148 428550336 309046723 771616260 571565143 913340454 911422674 633918746 463259716 546663038 673147381 175543249 954419231 129969303 922631499 721572068 181916483 697936372 958825366 959841522 152917613 908864040 238572508 592374620 432389443 42888165 416836180 698418451 698605101 489176672 578484357 403570711 24878028 873595770 114731035 537441256 462736757 948147228 969091916 227493722 961812083 658999113 394419777 795289464 721811956 681724996 2455758 294736982 581045770 789158206 641825836 228036545 695450825 262083041 337073934 924029174 349109860 536564949 462636187 599559341 24879553 445612973 850276505 628921423 667675986 354329592 4627…
Output: 376390345925

Example 3:

Input: 301 674327996 82199609 292745549 70737640 450189245 668681383 904873029 370458457 363446489 748922691 166799159 716544998 341412187 345026911 492956806 270013747 179164858 407700977 875366982 546998546 196194143 837016843 703116910 428180284 72298976 703162162 705894416 914407573 97635707 527419732 631886509 527120747 335138859 310784324 737964427 742548565 951383829 739727278 163449542 762113684 641816113 984365484 483590724 637463755 625088435 548149783 889811764 330366906 850488457 991590767 770846480 56170947 603057775 521927311 871020945 535134475 441760155 493974697 710377361 339038444 428326001 695598831 336587835 930734600 89154077 921054142 153086815 346870612 284526635 725517710 357702635 128755135 561988645 700022830 292523360 327194949 608413795 612634366 247823788 783036689 51…
Output: 139246935875

Constraints:

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

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