CT64124

The Grand Facade of Thornveld

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the acacia flats of Thornveld as Cressida unrolls the day's manifest of ledgers. The tally will decide the next shipment. 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: 1014 883976888 671856258 233842456 674813175 13397980 653865458 602377649 150271816 775047718 658727698 641626710 256167934 440130750 563185336 112895781 101069669 143125272 218172696 646794759 295717333 397281206 200669323 721338688 972122936 194510567 319742961 156787652 202371171 593416860 422497316 72469094 289372857 17788869 394869150 477885197 303973010 712386378 25585474 248879603 459861812 492107288 642464554 890369299 860579185 932870450 557077189 421593686 263672684 341172071 966485100 677597442 684763687 987705175 574325235 879375089 906337446 14717106 140675353 1929453 770992510 134657684 985781575 314996358 617824908 20209306 978668893 832064926 43786499 517109460 468739076 937836738 335267126 7057237 433655262 871265544 466167938 356770446 118783728 496460232 251351485 332383…
Output: 5525322560

Example 2:

Input: 2477 194376266 116538980 473603910 689356540 754752667 260917132 768015268 802687417 240468107 69727852 822093510 345842776 113870595 695550758 125004530 620927431 957251509 928490578 704438284 565251660 15309460 727242726 735286063 271393804 694897534 168597143 471165905 413638780 339290081 873353267 628828733 877466758 380834416 959656000 927000198 349619044 563584000 198375919 559386617 994139340 599126396 597868607 58554586 155686574 698525126 441156379 890105954 779379930 569936360 615007365 356298288 413846396 382986057 719142080 178277984 180967939 540379975 868539170 851740252 393575592 401224040 641085694 11655043 421785250 354328040 711541339 703679914 785036636 70324878 273235302 731543388 601116781 8489640 130863109 851806475 818051342 351070623 438795173 923016665 394049558 16…
Output: 7427565628

Example 3:

Input: 1016 456895980 210542260 609231745 602711321 256104722 356109916 781343732 986255237 694510107 449798815 994353565 797589176 188963208 91138722 309809685 998400245 949809342 16373092 657897859 183734876 779796619 798717874 47359136 987627346 131796289 576963558 315613362 971292887 410032201 998916635 283043253 364960011 809546352 240416977 301182943 589667596 314143436 558523416 334901625 266215728 14683596 952765162 813042639 121134627 367844138 341513368 92110135 243846381 60176922 794039185 109298767 789011328 689365918 353063851 428001142 362214774 425056680 217662577 289904506 407675832 440851725 852703250 540260061 634922205 528977031 338333238 466310992 610924245 570870567 436001911 694958985 61899873 7276509 854991752 516262054 768882868 272320198 151109789 254620071 884664722 1127…
Output: 7269961478

Constraints:

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

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