CT63818

Theron and the Rain Ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the valley of Misthollow close for winter, Theron 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 <= 2146; 0 <= a[i] <= 1000000.

Example 1:

Input: 1780 228979 521779 187769 880896 716539 701950 608877 160995 553090 548668 224535 867073 286574 862150 177169 680466 765440 611605 184149 625697 28332 972153 298578 61792 97507 846568 405893 44510 153649 567572 568133 977364 546163 636415 303918 253656 971631 986573 596918 114394 484847 709841 401555 219272 248791 296445 906348 722686 257908 703784 974314 417940 454092 504576 676618 498047 611201 800681 646371 537292 701698 697210 616443 115679 250983 621247 844783 926851 265419 624555 298330 495251 30263 373739 58889 740779 561546 42950 602152 478468 608435 512552 668638 945728 710518 120163 744954 627076 61649 269528 545007 707458 668109 752098 164881 903832 205449 429357 736442 171717 466938 314914 260149 673769 665307 620886 929823 28096 247519 660894 96794 812927 741493 319193 550219 …
Output: 864160071

Example 2:

Input: 201 710062 704337 674830 523534 371393 964814 287479 855184 577404 479831 694730 824937 203062 501685 462133 272966 957992 557116 74531 58555 233354 602025 262877 875593 116740 6102 719108 515522 60568 457001 3413 667375 864914 649830 655903 959073 362231 66850 50683 600755 496036 251589 818399 549110 389320 521327 655300 606977 475881 496103 421311 28124 56473 664386 203029 317411 72695 345312 671304 338359 361335 137337 888735 243226 508612 461704 837904 592480 17395 139761 554670 764481 531205 320791 670879 458711 5074 2159 568696 971698 973596 447873 730184 584336 892552 95926 370371 706063 884263 842087 844352 57531 351270 33178 650012 632836 549868 959108 60332 954867 751312 883683 309162 872339 738332 607052 916119 795850 176699 36818 159669 387175 863570 975040 324087 934285 32246 …
Output: 85938861

Example 3:

Input: 1101 239139 217980 769759 765246 928559 938086 480635 840216 969787 531357 991467 81587 639344 123643 706592 191854 444311 812986 76417 269087 463786 697363 233850 508250 257205 876528 135088 962495 857744 869674 204612 662331 85472 809747 692007 701852 912442 547280 757728 958962 470388 583128 963334 638548 622905 36046 444427 161210 693979 83419 146375 130728 927890 403321 88744 754154 132865 338509 762926 33364 770192 893631 331400 809768 78051 741763 40983 289 301861 619 980841 393207 333125 249277 535437 859742 720685 779107 639307 648177 508769 276947 988104 991521 822406 441523 792185 582457 798515 247746 61395 127325 161351 964483 520579 875093 551900 450397 789870 505880 758910 59420 889722 545669 786007 230502 746843 134284 973285 467902 561999 91587 423560 685179 467167 736623 8…
Output: 543336357

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Theron and the Rain Ledgers - MEDIUM Coding Problem | CodeTikki