CT39274

Dev's segments Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the fox den of Rustwood; Dev weighs the day's segments manifests and starts the calculations. 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 <= 1256; 0 <= a[i] <= 1000000.

Example 1:

Input: 189 291651 894699 593763 371970 516382 697752 632813 487314 649245 280805 935816 878284 225067 780063 804842 476055 744735 542097 934914 618234 108301 942169 185436 966011 772502 785286 88741 194027 461651 60538 306911 45324 739163 952649 87768 906414 111233 658993 115661 115312 343163 713178 909959 996629 574064 383264 78285 69300 980579 232876 568083 578282 373253 0 319466 98320 954209 52633 611397 783267 78056 613156 556958 423744 375625 952338 837946 801557 56142 776929 244609 141018 345931 662366 183845 527002 805628 272831 855150 714732 16841 258687 313373 347051 691145 352076 701570 246893 299791 689975 249335 395272 48268 874589 681171 299067 546367 87711 584313 992027 733357 467661 36514 960184 737940 581945 848468 950561 642060 373519 641588 882577 857503 953948 908138 849698 207…
Output: 83632640

Example 2:

Input: 18 769619 542051 52342 518316 877510 350272 155792 402776 518407 839832 441855 384254 195866 337748 309251 258130 757644 911794
Output: 6774441

Example 3:

Input: 536 80459 494931 988359 386515 215995 24677 911772 67100 196061 704525 559832 324416 405494 866673 764970 562657 188737 890543 855879 435515 204983 828377 294157 52922 634181 15578 866463 140227 607540 695170 904330 254353 902948 41847 340644 547213 671475 696548 568887 605749 504338 206650 600116 807973 944114 183059 238041 348681 369218 738629 730456 636576 740778 43408 264688 80664 408163 152669 267177 179852 257435 767981 798272 908601 236080 7861 463468 604999 536148 680310 641983 207984 162727 873782 433589 470701 26972 87610 101358 85678 725297 841993 470911 190634 950610 414631 14413 526442 957541 81997 96305 690973 234920 495285 49186 559867 15385 553960 899307 797563 796524 786157 113748 283725 994605 660548 25896 714988 362043 684264 137358 920341 787984 738857 746249 502338 458…
Output: 250572784

Constraints:

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

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