CT60894

Hugo and the Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the mangrove channels of Rootwater close for winter, Hugo must finish the ledgers ledger - one figure at a time. 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: 1088 767344124 807853392 263849661 826513659 423713561 42750612 82670963 684341502 97816193 294417862 621822998 418459944 367398675 522728796 250160488 722743991 143486660 403892471 24377913 417447666 734731313 686076181 885216106 136573112 22664058 532468830 409665380 663095079 8836079 237916996 886778251 534063326 915953763 955897607 223788228 745768122 200915585 611498926 179039356 845468912 27998743 665397899 270918276 811660604 693598655 58801889 599564776 354916232 321060028 399923594 811415892 808821180 58719212 318255520 514884813 644911825 437886572 14693472 19482551 484367448 589964580 153451162 356686093 639990460 507552363 837058721 278130808 887822867 112118011 547304865 187749103 845056782 609849943 975059172 89938073 771541341 500490081 264884146 753123097 916475853 62020525…
Output: 7846584420

Example 2:

Input: 1286 661419755 291765564 720979925 113288649 412925360 337457554 531383695 296984811 82352915 214246364 122598615 868961000 529472019 328962128 517328662 925646772 316322939 407743844 241171038 101921162 881641168 496939514 874830083 21513732 732005619 398634006 601207559 913413400 20435244 72295255 802452183 413466869 770437411 456771089 846794017 264617348 555519309 731360427 163552627 97712367 373243310 942383139 710786757 641919536 698091940 978737487 193372804 827749186 213923543 366477293 928476667 352410464 274934180 898484334 772963448 222954191 899936155 453657199 674175041 972512434 69538469 175472000 570864002 982112458 431695459 583279087 376395580 74640587 586637954 964605965 69400571 221072882 853966498 463881080 650252975 223493598 766797379 855759379 344646588 600064379 764…
Output: 7933608096

Example 3:

Input: 2810 426309586 562381201 213507645 361895013 906310124 235921849 659410682 412228376 409217436 120768848 395904500 533367590 981942685 760307670 137001412 65082955 833132074 772830894 221405023 2314010 565387081 917327836 742774953 324780804 90170701 937295654 363631134 649414159 603082548 756426608 140989471 134732695 106201587 344760820 134959026 767459859 617305347 858228188 312569068 78131296 981972702 617705878 561586634 531903567 75283165 719825393 715219876 243170820 451312092 604249125 420977107 759073249 638479421 467819682 923828829 699878355 198005104 189919233 798221490 277062601 855610582 137037840 703027439 257068884 241736389 82195835 342735354 910040318 308613818 43352976 779848365 856862076 322158308 598251382 377834823 534485561 353508878 899468140 8515305 782782190 84780…
Output: 9446055634

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Hugo and the Grand Facade - MEDIUM Coding Problem | CodeTikki