CT51560

Hans's Ledger of stretches

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the floating docks of Skyharbor with crates of stretches, and Hans the auditor must account for every last one. 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 <= 1418; 0 <= a[i] <= 1000000.

Example 1:

Input: 191 970355 798668 320798 665969 786703 489644 180719 10029 94172 422707 284525 567738 329186 557554 333474 40613 368324 685628 192194 810881 604506 545932 350118 794978 163664 587766 314589 905984 667532 469047 763389 675021 938617 370135 340670 591868 993267 358676 31791 795568 564449 830575 196049 427557 650763 580903 809844 169957 11042 912749 419871 568530 376652 158030 681193 437032 776188 616509 292247 872689 86806 442421 39108 625437 477136 577653 303276 688457 623089 159380 708907 592017 884747 930199 892044 742919 802022 138205 716002 925020 537254 310898 289748 190538 883581 208393 115681 355788 127212 710009 112921 470382 755462 34602 109338 809471 976972 257190 327578 321767 715394 127814 541857 909709 71490 592853 559091 180229 856141 728942 524815 229199 202460 318753 838928 …
Output: 89201215

Example 2:

Input: 389 863030 882343 565302 764503 585450 145806 683375 888720 618460 458710 993849 239655 113600 106332 384254 187724 448843 321635 4939 196976 87987 233517 418526 83793 143333 981400 751490 79133 548637 760445 443789 562236 622968 275262 910519 818981 587970 529706 774188 461644 918864 766629 533868 648072 706428 583573 562573 335290 598088 331427 42651 808019 447935 271735 852112 616057 318733 328484 449074 388742 326947 134242 31330 667887 594667 445681 756112 48706 499812 124776 466372 270274 323057 920301 62006 372893 763938 362433 922693 682959 473401 845820 183614 633826 812844 817838 806934 16635 606360 19428 798050 14973 33346 186528 443889 557991 608047 885805 75705 622704 203516 948080 991983 958336 727148 432941 207674 427415 947678 31750 33803 786668 312765 503770 697588 730200 …
Output: 186193473

Example 3:

Input: 785 128722 141722 835029 994994 443542 826850 903451 828570 486750 844434 777202 911151 607371 438431 321357 117050 291490 707141 774609 776489 565871 269685 977243 632508 910976 820546 30144 319608 530704 119361 101064 901729 749200 313844 470567 195412 113257 220222 333994 710886 380039 523059 108762 839077 914618 639969 197209 999527 583381 646557 598719 513039 688657 59466 586107 405686 972878 258186 335199 583406 870219 278032 187067 197554 526092 610115 306027 283208 477416 623813 429991 114181 266195 713330 675098 597647 686044 953414 397218 451328 814167 502094 265298 826113 417980 974425 692257 491996 130738 193041 984682 670979 320884 140053 350057 645437 629387 698928 22063 339086 450963 846541 166245 361247 500945 385243 435124 517568 925618 849689 880959 513978 63951 8351 7665…
Output: 384891336

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Hans's Ledger of stretches - MEDIUM Coding Problem | CodeTikki