CT59449

The Rain Ledgers of the Silver scrolls

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the acacia flats of Thornveld with crates of scrolls, and Trader the measurer 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 <= 1697; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1157 162372510 388722399 423728744 687191441 232867868 929778675 267192806 919272807 732298440 981283530 829928162 833981110 256029778 994133829 122937842 539992432 640816458 739915591 943196590 635416382 550970760 519228413 177443313 909313042 452544725 41558434 79352740 120330908 216755434 464446038 608304693 247269894 155619308 457552198 96674239 882838402 676826450 453237799 659506704 984805944 542726265 744948251 109913008 311001026 651650863 605662627 683972454 868595703 325872628 50374970 488677795 220122815 234714420 470988505 255386778 715112132 998016054 379247461 446927063 552187063 441583534 635692118 903416299 283802291 372956780 988899609 913854470 491055086 358635674 69347323 779130764 803755164 912058349 660832098 731658182 691521568 331666615 516155626 861007981 497630493 …
Output: 570448935116

Example 2:

Input: 379 529370382 931698257 687449649 800759172 771686143 259889225 641805174 520664656 780635612 125157571 248999258 984347915 621093559 366647962 86405233 276280614 377951128 375198275 105601341 793953250 874591524 941205152 416205906 716781801 632292070 933398551 490413361 582144107 917362537 661266261 717031756 93581419 391557620 818784275 142070533 226957629 88602892 997163395 212981957 297470275 647847718 325067389 766995360 735263743 687234694 788298457 282512822 386440175 808522607 670669217 621289164 244187851 331434854 297225852 532466008 66908676 364916665 535737435 929179472 813970184 483179832 283217482 768342259 15100554 715370362 407482351 143965362 850228149 319705857 283103127 280681985 839789014 878827429 614871856 521468069 480898018 802670004 262885533 800077027 833140897 8…
Output: 178748902257

Example 3:

Input: 502 598444056 554016919 666338783 565796944 311918355 288483622 682338486 788283523 48954592 445804250 16004531 400571641 710384857 284978926 779993102 139075964 298755177 845593162 949598882 771045052 456675431 690138796 744490819 436513758 486592158 662469379 106777027 411666350 71931451 664669862 536636158 68063352 808455763 36633926 514226383 539891599 274422426 210769008 237275528 830490803 774392513 94550163 487012032 114610459 748170469 55634526 968776458 920295808 374590773 648417893 127893689 602842262 943219050 37528828 595091871 651071264 46975334 643026218 154092656 138038247 801812993 652737304 888969661 991393547 757167142 366264145 869674399 182163692 634914927 609085810 118874809 377212066 954689965 978012959 813871513 745323937 802543602 120048439 480990031 909975765 73095…
Output: 246582945200

Constraints:

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

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