CT46345

Chetan's Ledger of segments

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Chetan found an old ledger of segments in the gallery attic at the lantern lake of Firefly Mere. The margin notes pose a precise question. 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 <= 1713; 0 <= a[i] <= 1000000000.

Example 1:

Input: 996 244236724 96612253 29720414 172836446 558212948 177343069 342485536 289402585 869292344 282738858 424651808 904810579 79730339 465595773 267222388 694074303 524404022 928184189 425604477 227547689 525616982 533240611 351154103 340679431 651124162 18518910 461523948 610331243 869285753 174884591 4104134 217922264 841397841 698208334 209220491 348722066 489150810 181755305 222733539 605829070 428155545 335136319 547411506 421447008 468227481 927772150 197312740 35148880 400020869 274862382 797962450 966697779 209609281 652304927 558736892 242318584 792561320 230913424 500767753 499507136 8323059 622120151 526440501 302119729 345546879 540448386 238970892 90998432 611897780 24143188 653439248 505763045 209966729 178960802 60438083 198202554 805977121 218294793 273128962 160320374 62511250…
Output: 490465527222

Example 2:

Input: 1435 457440192 797810530 542549292 904335807 846200396 158337883 776335097 326636289 293509811 99514151 451107603 45095371 211978283 773888592 525364686 296843165 597060645 613298534 719409368 714344071 255233501 740279079 919210409 621250783 288917614 958101498 472293201 753099246 895220532 638605370 489706686 477017325 222326669 247017187 909725175 606301361 515222082 796273276 343686261 430666612 868785314 999194227 848994689 515297370 399148494 990619575 823179853 692315277 376035799 889763214 258301209 173004985 986750409 635219353 258802834 723953556 211405691 364242344 97503078 948368118 661434477 460864694 819388415 680611592 323677486 889392422 272800367 938400606 74296068 2610860 689220584 764008442 486983017 439173001 531106120 347792084 615048069 702748508 314451267 555205074 7…
Output: 692794627703

Example 3:

Input: 1695 403228191 394863461 84002429 843243730 193047204 980498712 4679704 593352065 403364478 730314036 722221076 802870933 155786775 192923596 407362820 876787215 842461498 273408789 215547117 368873735 526988925 713890322 911163422 336303304 167335747 368674252 995168913 958180382 946922345 819337160 281692627 637514522 584412355 168792406 260796092 420875027 567189850 768786152 472689963 441202120 222662812 705447652 396106056 980083683 3196346 676851144 988053496 632368119 214930836 767090340 975460621 699045396 291931691 430023288 243327634 477957397 192799914 505562134 448836382 826493764 238398537 598399657 245864294 452702476 384634654 174164173 639402267 393973416 242377512 621433188 231633097 498431859 947928121 940977153 371478021 307340559 636081507 498212948 827488702 472144472 …
Output: 824165392805

Constraints:

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

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