CT45643

Sage's Silver segments

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the orchard lands of Applerun close for winter, Sage 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 <= 1218; 0 <= a[i] <= 1000000.

Example 1:

Input: 673 937448 986028 398970 470299 460889 817991 929456 90750 953703 109457 312433 84994 99495 881254 673731 921059 930255 427969 488145 614917 21645 515295 280856 643422 30032 585542 728229 297437 768371 834263 969857 308518 491758 866821 458056 922572 489024 217676 643772 503252 891032 657707 434973 540253 833222 178669 206221 104216 745080 757006 463964 209267 331964 404568 591801 471077 923568 81521 125044 584206 926651 887259 735131 336098 777230 115347 361220 216856 161222 556299 853920 761772 782033 129904 219492 214902 768874 293253 403149 690851 940538 481835 443258 542714 82927 874481 828575 961230 369179 173635 733327 122166 884556 843161 799087 609391 386159 431769 176079 510587 298935 450920 601464 128711 946089 324055 866352 620010 412440 131511 194099 313812 743927 361233 19047…
Output: 347118959

Example 2:

Input: 897 934035 99379 874566 761498 830513 606599 768287 797270 904986 832289 640824 157513 370527 753054 602246 380981 328554 781007 381158 107765 968942 744045 782985 294111 500803 539244 840923 845233 185364 881610 464654 107832 76133 519063 333450 285895 923620 42558 403949 371982 135348 196988 707954 483073 638899 994997 145019 964776 269710 732481 556125 885836 490716 30334 480951 395083 394495 796799 361635 175977 939532 239928 373996 854020 581250 330141 221803 397304 548370 436793 547955 456599 932689 305981 589702 490979 517928 919677 600045 577404 367713 619565 855223 240539 206256 63197 790472 215649 681911 184983 510003 364284 292915 912956 973742 881129 526929 38126 884929 101229 541316 98970 359668 995165 50590 306007 652887 129204 636810 450471 772576 413999 905768 32183 844640 …
Output: 433527507

Example 3:

Input: 439 3477 644022 887902 9217 447421 515003 171818 557440 315306 109123 111294 777813 854377 95500 299600 751133 232908 199283 536693 637576 259710 704352 795560 328728 262364 259428 937566 78015 127913 276527 753643 54754 588893 782669 774723 678172 577396 92608 261829 116582 805903 932260 409142 636051 201463 739637 28589 457764 294041 809085 322535 624145 626558 863825 34067 596604 61813 526190 898510 372084 383517 420620 805446 672282 789023 513597 511220 49736 304615 956990 435149 340433 475936 634596 123668 826469 662419 474788 958002 658685 250605 814854 239514 419618 603615 540245 546559 997347 666476 861726 439476 252788 942353 411989 49576 433128 303301 742664 164537 209688 887245 318921 357471 291814 470514 889638 389928 449302 383795 142146 757643 663271 478567 694877 602205 3860…
Output: 204840572

Constraints:

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

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