CT50586

Wade's Ember stretches

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the ember dunes of Ashfall opens only for a perfect tally of stretches. Wade 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 <= 3785; 0 <= a[i] <= 1000000.

Example 1:

Input: 1214 655621 313079 785917 930465 201396 223709 912688 242895 280725 969729 418516 492414 870330 400227 762728 52987 219198 86997 601868 173649 591427 135733 700294 856989 933267 29838 892712 64762 51520 421390 436204 67075 656488 273313 843726 866705 599541 772190 846074 440610 973093 58240 919048 275091 206882 177011 686455 602041 202069 186785 555944 602452 944726 702611 362577 846229 204655 750607 756741 121389 916082 515860 314252 665750 524402 724073 472262 324539 108812 24791 922640 940697 296718 692995 714509 763604 423075 252513 76525 255215 79189 670972 815982 487121 170225 879861 137507 581866 673228 339241 107064 165634 397703 123161 971458 547707 745123 97373 101924 810613 742936 399468 505474 228827 336812 738761 954882 995476 760361 439127 134511 290451 219702 624304 27305 94…
Output: 586423098

Example 2:

Input: 3044 396133 26778 915730 474362 245247 111914 235946 135096 192828 385509 658793 550090 2085 932534 622572 343551 686739 21751 566052 168497 56517 308648 471083 891208 639174 958071 221454 980705 69288 378489 58755 902856 214346 396979 932133 473628 599709 766834 411538 859523 652987 52102 419022 508390 241378 310437 231693 774624 266349 386778 169923 316441 702745 279234 838797 374004 795699 389096 600643 233067 151159 964860 288521 131567 955835 444937 17175 494417 12471 811338 554862 785345 542294 572510 983234 363039 238790 155431 896450 68857 262329 854555 895272 716631 917391 421832 777979 802673 48 293011 812339 246306 88023 249011 959648 346294 182920 796008 767664 461630 437161 602887 773555 324113 74768 738485 293604 872240 791550 558569 563513 203263 630114 428969 543711 154387 …
Output: 1530546891

Example 3:

Input: 197 117744 934889 860041 481140 709051 889574 544278 718491 787497 636064 484573 225994 615264 121103 566122 272827 130709 598546 23012 474051 195614 634426 897611 443817 340497 117891 225545 646183 720081 249189 342850 457781 354898 530141 455361 669554 964906 612182 647484 443249 604747 888213 655995 985853 422846 513240 552424 953579 864591 212791 268744 30823 330869 249069 135089 88302 509016 47206 797539 602356 106500 410392 453664 837121 870413 231380 347726 528978 713992 435457 216325 472149 379073 728557 676308 899166 93066 139888 925449 620645 506962 951210 724118 564494 749485 277197 301697 930698 726846 991564 587778 948771 715299 541628 914219 599942 50896 43841 605497 129480 963260 547555 253341 19110 37177 369725 157950 354348 554327 350034 131812 184175 244227 532606 527128 …
Output: 89755783

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Wade's Ember stretches - MEDIUM Coding Problem | CodeTikki