CT64212

The Grand Facade of the Ancient beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The reckoner Darian has been asked to settle the inheritance fairly. On the desk lies a long table of beacons readings. 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: 2402 514920877 707963018 224193936 436726339 524246520 298572986 578166752 300338677 752325347 409844360 456932349 765483192 945684723 472766799 519235051 656204620 520352581 855409658 934301595 940097017 325006072 633762437 740696565 92903424 551273960 450503539 200418864 987594599 180471208 145617848 57311813 777479364 31635087 580796128 993017880 14952014 236039888 470578037 444151546 210525844 73441365 387457451 514116044 423937875 911844344 53806038 350609302 561624005 891851939 51414040 498720532 35316730 318396568 996023897 375161431 146777025 128552343 17582826 130576250 345296217 372313479 776364115 574931658 979959346 276550275 550424317 468936744 884236949 2434677 136516651 480454549 295167896 693897056 489344862 519137935 21084568 170179062 246400339 414123594 716792869 9455302…
Output: 8952072480

Example 2:

Input: 1909 325298533 344717390 695534571 943808388 958309256 151681317 938204199 980346538 152816822 578103803 192894918 710141441 445564690 207339539 470026058 196150420 186052915 922092100 964162988 49735150 554038195 719018643 286698065 952885765 47567872 887524118 313247282 973765985 109080465 852333287 881309255 794472459 419920129 78802627 704811049 748434753 738385332 754005783 762459716 898400381 317925317 224161421 962271286 150277773 805034612 569518376 234377619 324829547 450658539 368578395 466106485 117905695 84656604 587834433 555051518 293504577 163127572 423162829 884581430 281834746 350721997 159397311 693539734 682265981 301460276 173136556 154953330 941525725 167527529 409831540 58246829 613626344 316972765 23354975 976835867 463100834 716152853 498322748 639303949 975530461 8…
Output: 10493415225

Example 3:

Input: 3112 398719735 135808206 482052517 775736503 563424632 207101081 847570639 147608053 450080829 276829093 352937292 751044670 257685709 85840557 160210145 647478142 707807031 128464970 271525114 956904700 31293470 942308917 322208065 369962320 579695204 795989652 998577299 850480231 604026473 356605753 921639042 556457822 141867122 261747563 937840388 275366879 255066332 803488555 210995087 632074696 63410519 98895973 265460526 423006617 829837152 855618166 731855670 320353737 705857801 324911531 75334342 256505622 298200027 236267860 692168577 221121516 933652452 214606330 915102471 917208664 187125029 42161928 97061047 134916451 453200228 989786639 68497669 793088871 491000886 49771296 269923696 716459834 415060270 113160321 106916408 399813901 192309730 313229966 757707846 206558781 9765…
Output: 9371016688

Constraints:

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

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