CT54771

Jeweler's Radiant panels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the frontier camp of Duskwood, someone must forecast next month's demand. This year the task falls to Jeweler, armed only with the panels register. 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 <= 2969; 0 <= a[i] <= 1000000000.

Example 1:

Input: 80 200770451 62279422 252367203 504118819 899348873 241796924 585931317 271986224 24702736 431775665 890867211 741128805 400265833 404345991 821410847 390306063 276880744 174044181 118912521 453798095 978780633 866474937 955567928 557510439 186395975 888924992 927896767 201029972 84566068 555641927 455624924 645610330 46713609 130404794 104159556 312864973 768255985 502949451 529948160 333659050 549809842 82781469 287963902 399379115 280740508 563471369 941378052 144574018 144160537 82103648 496488780 615932879 387650514 787770094 796389705 43605976 390239278 191458951 719394430 184341324 548086968 979624716 624113093 31802663 995100606 273517779 75638211 660400413 94997633 21464626 648789751 292042099 40903712 944735932 748932976 588121450 413729384 500972835 455125261 100675025
Output: 35700585450

Example 2:

Input: 1355 588596448 88084990 24154626 183925421 612268808 816525932 575189103 524516140 413453256 779327065 11511740 752677350 910067522 390881863 506015166 415172844 698236051 307252894 420884300 362138318 124835820 96424185 748442928 384377445 837558717 426012230 438143961 850869588 146602108 769951711 222728200 55421384 785086356 724696197 999192581 449332025 694135976 493747897 693445022 997920123 692783153 237949558 593992112 538144625 487605443 27540077 363017225 309836389 528028534 750066657 707247193 229343656 255463717 484549964 821413941 239367091 709328629 517176008 593350346 647904349 860418159 74583719 871898626 539153152 111066160 407772198 817844516 223876164 263013238 262437949 852592192 500729843 793907322 573063673 318700526 504518746 37499042 622263248 214957244 996710234 950…
Output: 667556238402

Example 3:

Input: 995 582360697 394588113 590302911 403405742 469367821 582525676 69466294 405655197 423487969 223607047 464228501 596639888 923978109 715150821 706746290 614770407 373629629 368144431 904939628 485284462 487545307 402536812 412346191 648920751 725449268 366329865 664778494 175695004 827409471 494769533 720943145 776631585 63139646 714914552 155481973 417148584 543932085 218295266 677298117 441787865 269764296 947226552 190069878 714493686 822889988 617180326 134974228 527110721 638236105 366459276 705289962 490244135 291883284 492311993 532845929 213676783 610250154 519919492 119052078 744798395 105411482 869842507 552462446 61290938 825607691 79397206 801652799 540116913 853626397 997238074 106674118 386982779 637868028 731006920 316116647 538380050 719238841 115575732 808437300 391363794 …
Output: 488465234140

Constraints:

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

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