CT59232

The segments at Amberfield

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the wheat plains of Amberfield close for winter, Squire must finish the segments ledger - one figure at a time. 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 <= 2645; 0 <= a[i] <= 1000000.

Example 1:

Input: 2266 175818 712608 19764 67693 417438 696503 609852 629754 35134 647897 465365 369062 831213 776161 56701 695753 262221 473417 852763 603532 758753 33059 258617 491274 270173 865855 600639 517559 451262 692027 324546 151548 364039 128721 718833 197427 838607 834225 792201 335198 692245 314087 340567 617022 322861 288940 502273 230162 82818 484417 339263 35777 69095 87808 470936 80390 922388 940037 849879 859137 884497 413937 325322 781899 486592 732339 132737 345641 700541 22375 624048 56414 72980 938727 86082 760779 2201 928235 987161 373765 455637 678867 937247 655545 865251 217426 336813 500017 462503 591433 141404 483120 680486 950034 490646 319950 673337 270167 459726 98945 885496 54463 954445 122492 807100 897916 750150 723473 142946 719325 662793 376054 563045 144026 562913 966301 7…
Output: 1108083820

Example 2:

Input: 1702 362010 936810 575316 549752 60330 885617 482523 535262 595713 622474 439560 979137 598024 724050 928865 355666 701240 610630 472148 810078 594295 50758 648788 421766 985051 342992 667638 818405 513936 475847 453292 697695 140849 268014 611060 320839 891715 704680 591779 838750 173573 949795 234613 849621 263958 693283 384474 56728 601238 309564 546484 406606 949897 921561 638614 809948 198029 167560 847049 929276 27486 939192 858634 343080 91201 217935 477960 63202 743881 111599 666579 607534 804432 879468 252249 73679 592240 336012 675953 21718 887177 996249 986343 504734 562407 996333 471848 302104 485109 206989 851604 726793 340480 745071 295292 569203 328390 605828 297257 362069 391686 270365 9698 497418 722660 653964 605911 118009 272651 660352 779200 742025 600702 459516 945662 …
Output: 820110078

Example 3:

Input: 1104 715612 191277 483849 549053 564671 895873 239038 943087 882214 159080 853128 216008 164597 537372 699128 728711 664261 489021 393508 874000 414253 877943 131230 361444 966176 900178 734567 511773 567470 451410 305329 249737 122217 633868 556489 212658 753626 738622 961407 656474 296665 863817 431140 621323 522189 272571 607290 662014 768223 299155 481218 471232 200766 756246 621936 275806 982528 905055 362747 726003 549785 109250 467135 969274 72638 12410 14709 306041 644420 779948 456447 194704 799072 837236 320044 750108 875579 195315 196772 921384 442698 902244 394712 884134 698131 187365 183014 613545 266546 494768 815418 385030 970308 705232 485290 169222 568407 982517 747203 89436 291882 596477 922183 79950 692247 930929 134051 248082 568518 763970 33613 477139 91598 597271 3918…
Output: 535723075

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The segments at Amberfield - MEDIUM Coding Problem | CodeTikki