CT61077

The Ancient signals of Rosa

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the temple city of Sunspire opens only for a perfect tally of signals. Rosa means to find out. Task: Bars of heights h[i] stand side by side with width 1. Print the largest rectangle area that fits inside the histogram. Input format: First line: n. Second line: n heights. Output format: Print the maximum area (fits 64-bit). Constraints: 1 <= n <= 4000; 0 <= h[i] <= 10^9.

Example 1:

Input: 1948 325875352 805703063 435724056 249929419 264568944 125042531 413795091 546296558 259182299 753667786 942102280 30067496 496443808 678808055 27937897 671633936 620970624 651670015 429957020 594237948 120703194 580986567 407895809 816613997 993208606 211376396 488267899 730264976 973355382 629718560 421781261 148837869 659749519 140797794 458341259 838234515 838289283 345704984 363106840 471821958 317004836 73678165 945131128 177739148 283676891 795531877 120026273 176018853 586477463 214157670 860075311 535529943 837360932 93365762 507095216 985817793 831108821 630987881 290238866 367287369 961972120 180649218 140161570 959759447 673138108 362143619 8348637 180278585 754158780 184728364 977934168 313543902 463220417 647096550 984829385 481774070 32558039 811004510 593159429 139810627 25…
Output: 7783272960

Example 2:

Input: 677 74955008 878185655 86247716 844644757 896534253 319780279 372404071 548119646 322017215 562728727 778649472 632009389 80375813 274827951 400687282 561504618 74429026 747144057 673197868 983281288 195386984 155848752 213568451 551185167 639752963 964822124 694998735 76889219 259431467 136091120 11113744 133773550 540258654 592758864 955277669 709555909 897572996 532088932 675126011 779146545 513859004 129021211 360255804 104395781 415996848 122672008 43385758 227354486 44709552 942793351 504614129 616309755 689026644 702091939 469681965 368803305 832463279 609758552 171812665 288923490 456915846 245174598 837673927 779425356 240035681 759165150 383618215 130447000 602955361 91539608 798931057 765764857 212970297 564066194 130987782 152299683 662279615 193299819 513354335 518541489 82298…
Output: 5971232358

Example 3:

Input: 3752 365270584 965736048 691591557 625077962 361802052 620552466 211449925 779390009 984189629 763858704 779415543 882314018 738362337 738163680 513784717 863029998 408405047 992139797 595686373 189642961 675635280 51499356 821179170 402592658 504568774 86665267 839528975 905173454 122275751 45468559 91116064 92975207 680964125 622397562 669257854 18662182 354397991 339170844 38787029 295948663 580857432 869533084 720741731 510195535 416091010 598368014 850905087 388643820 291209227 590133153 702328715 710985293 423839824 745409525 204490561 834803056 671867051 105147260 932513483 138061830 329944366 691563782 162536358 821640340 912693995 967898829 494673680 76070162 412606406 796327767 293407316 258769622 268475037 483019212 727078437 900909310 795095266 492590926 61328136 524063430 3720…
Output: 7315003484

Constraints:

1 <= n <= 4000; 0 <= h[i] <= 10^9.

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