CT62965

Sona's Crimson stretches

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the dune sea of Caravanrest as Sona unrolls the day's manifest of stretches. The tally will decide the next shipment. 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 <= 2118; 0 <= a[i] <= 1000000.

Example 1:

Input: 770 458321 389293 892850 961015 482364 120189 395070 871138 527071 405966 125019 249783 512992 670205 639966 289972 45096 673642 644536 889727 175451 41681 660801 145918 11035 186502 119289 501548 482207 812150 524732 588263 943963 782564 295906 410933 801288 890936 28378 48839 14485 927021 881703 969394 530942 883304 2606 855212 954655 751642 14878 975588 865667 283047 66515 211140 334369 415693 220076 395424 169664 975715 202503 283326 723224 955627 209881 415249 859754 382370 42795 920300 639394 130221 291277 351372 90656 999588 544807 581222 387012 918444 761613 522265 113600 148508 18963 861552 93239 124357 880303 765692 141543 210011 678810 582969 802016 71314 179240 195970 644713 21961 215151 117514 24914 25904 310633 725169 244589 459586 661082 850468 147680 556550 37164 887083 541…
Output: 364575009

Example 2:

Input: 1650 643073 300417 326732 703675 330648 705270 228751 300229 238229 485142 51831 512512 685482 214829 290218 450134 365334 981660 773694 900106 572987 2439 544461 882877 748287 947380 39780 572057 764812 673383 273043 581338 503889 493123 491401 581833 561400 971647 461345 11033 181901 21638 666292 599952 403020 334527 433004 698770 512555 814745 789824 551337 42090 18604 785847 559049 745890 946392 169276 96372 108480 70418 413837 952995 405560 734175 212163 271645 214616 70094 941233 946225 643451 96152 785951 433980 256381 559117 533206 48380 60402 24925 633603 319430 179 671046 5889 112841 607569 970910 279907 433430 155014 914975 923045 64561 205385 71645 121129 209323 887039 556767 229579 597252 967994 280057 735104 152864 673259 487665 858754 163163 80538 887270 21907 493855 123072 …
Output: 814700279

Example 3:

Input: 463 675885 341913 867009 625126 259478 530501 385515 798457 641573 861784 759259 864671 828140 229528 836809 127872 172904 614735 768584 565853 309210 923012 550073 239828 599598 268351 824260 66185 151587 957271 383508 481274 719877 131652 499609 335885 970538 86236 869955 736057 158330 747474 473106 582116 433898 960614 743859 221542 367953 707042 89483 289836 947831 774150 245992 207659 620556 18266 347898 878264 135651 408444 347165 97548 232135 998350 565324 814511 457776 410695 982492 561338 421726 486681 312728 252512 535426 65451 216229 336828 588688 870283 702530 438028 117057 647906 679069 407300 724787 175258 517926 388894 462308 479556 185526 386149 349066 311334 467914 386699 347533 491299 237848 694759 774511 816657 737717 32329 357559 517557 482097 525183 450952 406979 36300…
Output: 224504733

Constraints:

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

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