CT57265

The Grand Facade at Amberfield

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Neel found an old ledger of beacons in the mill attic at the wheat plains of Amberfield. The margin notes pose a precise question. 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: 2528 686283057 470993158 219007445 651987604 257497368 166237427 615391560 95706610 168709647 784744775 661079323 820964081 309886782 651072829 78601193 645592348 603711887 535752937 123114322 42744863 36876308 808128783 333493277 25309436 695999230 172546661 662802021 13859396 868043883 664433247 736616369 560106049 383310381 941783164 55592463 529849100 126860319 30486458 633236616 801587770 827071448 924716310 236935009 950477263 506520098 460415782 445247663 346088807 729026031 341623216 961624961 941824027 135227039 929013887 459388180 198958005 48002659 90853196 269557157 68915584 286539486 106887949 938378996 693469389 491513108 279146555 635805620 756916480 430296457 171620218 609868931 389799247 622992655 480010209 963250064 301788423 587016236 96662355 421494933 161452936 1160765…
Output: 8977882698

Example 2:

Input: 2096 867574370 321087979 607089874 354007979 268919727 104950291 492442212 272005395 465808356 453263493 260347816 831573585 961328950 416425447 658876551 703537612 554775448 997167809 606736513 536344897 843131683 504348421 354018877 135316891 520039828 184992668 542377000 653961595 99499028 1400792 580368942 866977953 700180640 707085493 287537573 966874006 739529001 870918601 599145496 128476806 123396915 530930274 316968596 825603028 868835426 573509403 609873280 987835334 520014347 584555564 620343094 673559938 764775098 388577386 18818255 312884662 664050109 322119526 886786770 962284943 744394525 194223582 695429789 547994324 719475974 419084295 194342607 934675399 711295250 699947787 382757819 40919633 888886356 919230396 164963011 369789935 996304071 252393353 780288350 329484887 …
Output: 6720106256

Example 3:

Input: 1918 130726422 826806433 114102631 466918642 961494428 188579879 140437092 320968611 927399427 666228721 452645953 909356268 806124172 612114373 244369251 960912994 48904833 696325614 40304685 285153527 401264515 427302778 974972763 620137144 155157610 355570662 771438557 831082447 889044239 821286884 472825582 678716896 671951286 355236678 760751244 95057781 213999330 939428187 977758786 156335416 916785149 342569908 933487748 594421072 596821459 529795243 743477756 720671829 167662491 38359832 358183811 990209527 891738464 293199078 154215987 421937364 676701834 470354322 554008232 598691167 382256797 295824852 182818523 841308789 828642816 263886079 47355795 246854923 625905457 556775217 328479856 876712084 596079043 718440579 853386197 284696964 442187369 707186108 13492634 817691238 1…
Output: 6601939011

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade at Amberfield - MEDIUM Coding Problem | CodeTikki