CT41746

Last windows of Yuri

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the river town of Willowford with crates of windows, and Yuri the log keeper 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 <= 1322; 0 <= a[i] <= 1000000.

Example 1:

Input: 1299 946685 116775 793998 420652 851587 762085 454541 132172 572950 227560 986071 244481 941750 820915 439318 121582 548669 300789 418560 773655 174922 658658 377774 560576 210465 576384 999575 655245 431877 776869 518671 986855 548922 480974 934799 430981 407397 293146 469495 440858 61134 371732 801310 602077 21194 738812 622270 495869 549059 287344 615155 843855 134682 644029 630100 301946 426262 609365 820133 103066 68950 38243 137798 548109 845058 82150 404955 443102 641148 245648 140535 31199 372865 441363 377554 183175 388891 69750 824747 903525 40177 552756 332218 913270 138169 91446 990745 903955 991262 900484 109962 835589 533967 361451 405214 181471 476046 542106 737465 895148 952653 797732 68499 589674 336500 271905 542316 60036 795595 961386 826039 376377 470983 260257 275932 8…
Output: 638946486

Example 2:

Input: 1092 461199 431983 179259 404953 969041 843859 731128 69698 997598 475208 907010 281302 934832 410977 927338 213761 949637 324379 577536 965832 886016 9977 202956 752068 511532 135927 913741 982298 630722 578267 140785 458106 758583 396438 290294 294460 826090 566487 727423 441249 365309 605215 237464 844969 431457 562085 948046 952094 215245 952146 890803 999280 595151 270739 430228 954289 259675 894850 394658 508874 648110 739761 753049 793743 471324 980998 488896 254560 988243 778484 312406 266192 703183 121682 15010 496448 332185 921302 964267 203279 587380 413211 131205 730913 521444 423372 64045 468240 73004 879511 230889 681734 305778 449706 222532 876701 413965 777577 913183 634867 407898 161187 905874 415438 395123 204695 355493 219730 208600 610536 785037 703069 72421 572632 8745…
Output: 520939031

Example 3:

Input: 662 206015 48819 688127 22016 281134 502633 121773 586438 599549 540315 188483 453739 951070 280485 526362 107465 934068 95716 828382 826812 52566 571259 899217 87393 834825 410817 846196 237729 79765 360263 159672 311233 319193 954854 604850 888305 991180 525657 331701 310126 916265 269708 146611 82911 516941 269695 497882 187245 966814 523289 985534 190737 471428 325172 498729 366820 527243 921152 207585 391489 260784 753695 948159 757695 83360 213549 410030 835500 45680 517502 416930 944620 53565 520337 717297 609337 660742 384521 34686 766752 482534 6098 625079 481290 521097 625013 625116 411520 867947 409886 241033 839573 752612 974149 967518 772879 350191 180398 546092 340472 724195 400692 103350 582417 375908 618395 354221 991579 948492 746251 412820 997940 198448 926499 552623 9956…
Output: 319981258

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last windows of Yuri - MEDIUM Coding Problem | CodeTikki