CT50855

Trader and the Ivory ribbons

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the trading post of Goldmeadow opens only for a perfect tally of ribbons. Trader means to find out. 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 <= 1879; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1591 470220652 128936850 716522847 375328669 652471601 464216009 894383769 543996976 634531295 386169747 254838609 167254969 147851261 282975711 115037558 121501162 83701212 495738860 679242301 599179868 181985623 322714355 66929594 530423684 208882245 730079581 565063484 78934764 439539279 597547687 936654700 35850358 449350724 411089179 950783620 757095887 474117050 365289702 147132094 723871070 776482278 229295131 332008040 416874034 847811609 984897161 592653819 937625729 521569558 822611832 165876617 33105955 909234410 571702911 592518734 93060098 48643704 339840812 304440633 308245541 437569893 943221767 395774739 538924995 200513954 724810903 136911497 546111014 788775857 13301714 660442850 566713546 559596316 3222935 947305143 115840903 102762305 843662488 675491771 717320326 14891…
Output: 793756637935

Example 2:

Input: 448 496098411 439268931 97311585 743597876 837682137 206212364 202575199 841088811 238048785 916074553 359337131 158264411 966271554 69683756 182217066 511305051 47854232 369003741 775316306 440968009 798523816 373467000 41308062 761871509 299642444 196131827 17352696 36348424 267794001 84567585 290724891 296145089 314729956 359461525 108503403 557108893 38256976 280874311 187710071 627850993 103779499 430326301 45333135 932255283 228006139 910599918 551929792 809938336 537053211 739827381 351536445 743828339 811582017 316685715 144083346 816433915 445085534 289461058 399600974 600947046 983470060 731860936 186617470 896881551 407775430 753058909 983004351 45523909 231354778 754862476 53660891 640869971 378053238 281272371 87284623 756406606 648845282 249796473 792863649 84734879 816885344…
Output: 212497084338

Example 3:

Input: 413 963412958 156134385 952834956 126664501 79844142 365487334 376013300 396805648 975606744 749164271 971740163 859200849 478769303 268577509 170366505 956605520 594827482 21271210 824420936 729891503 714862981 476230320 882435794 760757104 885979116 345592179 422726062 626303867 352050074 400852316 451633203 458089367 822702271 753371256 951773836 45455585 958370778 117225658 916779048 198832806 719312028 293193355 502114358 403246150 868883792 772459548 256544287 408192444 565703344 756782986 179042953 162869018 67833565 71978426 928109886 729443413 319175821 658467729 642255946 689083189 674468154 342184080 813373792 168268296 463853187 419787740 510164325 624625725 815822973 827888311 715843356 792150492 93611611 399754991 551198394 171439105 734340103 173860783 994783055 743602417 28…
Output: 184778983161

Constraints:

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

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