CT46235

The windows at Keelwind

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the shipyard of Keelwind close for winter, Brewer must finish the windows 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 <= 2857; 0 <= a[i] <= 1000000000.

Example 1:

Input: 2781 477877347 750472525 937022613 635936573 706202807 717872127 926005602 73181292 874882197 887289823 411944539 7634223 637216183 884266632 836659240 939067486 889878680 215938505 483757276 154891008 858951220 325682538 966022190 918522560 958996586 459400916 358911724 670446891 835167275 598852362 656959627 586706983 133770838 538798478 578320441 106045191 313297463 515338975 856170544 784915172 593319470 90295876 258720710 777499942 584105874 125697627 694139371 111285762 153667149 53857949 79227725 15322341 468335112 850900492 328668171 557871439 398611848 3003473 548882772 499684449 183045912 184759397 741678184 83407339 181881428 940983573 673671031 866579712 219542602 695769987 972404887 984577010 93098548 776999091 514604627 374917230 853281642 247910470 446085945 952168405 670411…
Output: 1358177848069

Example 2:

Input: 2180 979904198 162674063 655774677 770642986 859537656 99970353 815248665 32599454 364110314 425269035 243127405 947704472 669330414 581711883 267659617 103521244 945439342 280944006 828933998 571615412 192561792 945426034 781887616 119741124 913770090 179631288 897497218 81041062 687416557 624540507 557658517 734081486 582370620 730438468 864957423 197589923 966273166 163290615 365045868 403892047 725840629 230773078 268719156 875528118 215245850 528429715 536974674 162683301 160778457 971767465 408204636 622784444 923901036 619189276 267012257 21678955 292375095 873379963 294523074 270695124 691979016 360739122 777569816 392539663 530612391 381078329 527731442 649671459 951216568 398947228 921839109 472072129 992480863 189779527 517529378 68427448 925260535 853090697 836356626 595471456 …
Output: 1059482718651

Example 3:

Input: 732 269360540 9450561 670823358 563458352 665711356 697782168 799156904 897782355 375922628 429282023 585564749 45931310 734990046 116586270 17973416 741315133 707698474 851981116 475909842 177547062 170695637 262257862 680409765 601985307 444034875 928711472 311940808 832482265 83946370 647900336 966251790 29801843 983911367 528192100 181870339 951259482 711498727 435196461 428826702 385446598 88137166 703359681 238388692 548310881 974518717 625561763 208957498 122791593 960168151 30109838 213859396 154212138 444925562 11320255 539464179 650125414 999894334 553069161 253454390 732615120 972667104 792573766 801494988 950368714 471574074 824268299 194210115 533654261 963175374 936437325 682089951 193158611 129526613 369755868 376756553 722007508 16494022 36882096 927821471 571813159 5054926…
Output: 362887121530

Constraints:

1 <= n <= 2857; 0 <= a[i] <= 1000000000.

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