CT44313

The segments at Frostgate

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the northern keep of Frostgate opens only for a perfect tally of segments. Neel 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 <= 1755; 0 <= a[i] <= 1000000.

Example 1:

Input: 1163 667995 270897 342921 695466 170637 521702 781093 550544 35121 14192 721704 636959 536223 200025 130471 331847 274110 282625 381269 580592 520131 345297 231187 45716 879538 700515 375611 79645 474849 550086 94804 158172 240181 757402 167573 9787 48414 256259 673464 635911 428922 619389 858811 339271 504611 77525 625346 439147 673699 605411 441340 706520 701316 800373 663124 989824 661128 485762 575803 306702 254789 950197 983195 567412 885671 728639 917277 768442 811385 981463 567088 561817 724903 268496 374684 133991 28689 941768 489507 387587 282629 990888 14042 803801 539422 913705 497257 63611 537476 484092 60379 829926 545284 44638 50197 840202 356672 697739 182426 258559 160455 881054 208022 572007 36157 761544 106286 551598 940915 964118 585725 732692 689779 161519 915651 164916…
Output: 560405163

Example 2:

Input: 1626 191516 717534 925384 497485 746574 709971 199857 628949 471210 950002 840737 106343 874182 869328 271226 271123 122597 581402 999984 790569 707701 672990 171607 604846 371453 962322 975967 857883 930079 960231 867033 795024 164602 26331 741635 274723 342007 587931 356619 258176 609767 81884 743163 310206 57051 68857 452194 761149 385648 454399 137543 936525 500117 634120 978686 36073 549020 635941 936635 872708 143343 540139 198279 140296 128945 340929 572619 69968 373202 681380 107970 579297 777789 972884 846501 620260 381139 447953 108697 888625 644502 34425 884173 181978 582904 424697 159155 41688 42646 244716 727390 943981 122978 349224 978189 580448 359558 873220 814196 564480 80859 507590 974557 501708 798404 781188 953979 960111 216260 11476 639158 507623 74090 786405 100752 23…
Output: 796802135

Example 3:

Input: 325 464351 472618 612200 50264 935816 895998 758597 755142 953933 449070 776693 116741 79688 864524 324808 451289 21879 806662 768093 956357 116970 198400 879491 817923 335312 726727 172545 860617 453050 674139 107057 660587 941929 319972 758269 772990 71084 524382 968104 98316 820740 754982 334815 706813 213221 310349 403102 439171 838202 107151 319893 513120 24778 79482 14309 76041 749493 648143 260388 737228 401008 178167 703592 812723 725460 125574 78369 636897 86649 573835 633977 841265 700962 80528 84431 91215 576746 926319 426571 385989 889806 78481 962443 622145 738898 853272 46710 756587 334306 542497 155861 323174 498912 125164 788889 809605 208744 438550 814061 906383 249941 43981 731370 905490 175641 67787 835023 999913 762780 387245 538070 324812 320321 140296 71761 34122 7709…
Output: 150473071

Constraints:

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

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