CT65090

Gita's ribbons Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the lotus ponds of Tranquil Basin. Gita spreads the ribbons records across the table and picks up a sharp pencil. 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 <= 2783; 0 <= a[i] <= 1000000000.

Example 1:

Input: 1322 851916542 204663975 530594507 704731441 707057564 262771201 139036435 774763926 65393038 590793778 123487193 505575461 733187729 362127993 322088518 807892315 100789984 851486011 676278386 255307373 821862866 751391490 905292378 19823183 16506899 534121485 979805796 634499050 648842926 635793763 785433129 775412590 707887935 86487805 718355944 996084983 719048863 349498382 265749943 485165147 789290589 308915498 69848854 595744683 193496706 322240435 776128744 963196777 671901551 11117983 356557581 894390522 429346483 232833609 605700641 103551554 314716054 134016637 492880705 128748524 362174686 283377102 87978762 326049981 562458009 870534879 684453507 785554625 66792831 274407207 164090153 551050767 145479733 827597118 119399166 933141285 730812679 557090424 429030284 169972203 327…
Output: 638268123986

Example 2:

Input: 2507 116224112 795215701 955513761 696767995 981720022 291659346 812094301 27978664 177816481 299306953 1131336 880120440 157044159 722259899 861844786 169371505 260221107 763661894 336632512 380026064 880766863 659670433 979532913 317543266 747075162 324804028 600466814 169291910 113831915 146641470 582539859 878320818 695411478 358952827 350264732 500428133 88560501 970938646 223864503 916806277 473546763 395310041 811781798 781052253 441152542 984888476 980295348 608182952 576894838 237375377 146830525 702846217 2081398 702210169 138351724 315549259 603199215 97417 726562825 85549356 913911513 697722964 74073609 89138385 751295203 208196516 213542837 514886413 689716230 64563294 491506729 658111868 174979192 420527733 434697349 723614055 640074337 387353508 639511283 978350198 53777028 …
Output: 1246079058830

Example 3:

Input: 1008 341992299 363835616 526789183 593546799 54378508 867384653 567484649 427653092 583979318 460117443 978192084 489928352 948076217 354235705 601884441 839707845 287200368 604799869 837862040 964269617 319215859 375513452 159388898 509769626 55950122 20986401 480067960 5059127 515645034 424162194 633275357 137985564 862171253 277839953 836267777 909430118 780600216 132041311 295186351 727803156 648416532 668073724 959814971 503584498 977038177 450316159 757236258 46820627 723242308 38481659 505489172 505916025 991861063 338732501 581362549 195646374 815800577 135194832 720606955 121488645 867490549 375593768 413776324 640472285 266431996 89280823 955419593 431495415 408225972 58872075 626113523 233059998 106094183 289123325 44882064 448147848 850167189 285065717 115966409 850651841 98974…
Output: 476034102347

Constraints:

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

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