CT58444

Nandini's marks Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the observatory of Starfall as Nandini unrolls the day's manifest of marks. 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: 3675 715837383 593567704 304776274 559206359 966781404 511902485 466087186 611311263 384593363 636175769 337845962 768669623 123209830 216457392 127488971 822183742 67575343 126798495 304350598 613675389 980631939 370659596 814436045 925505096 574228509 769390761 390108519 767514390 592972156 136489856 372259480 705333474 565464305 726587850 683595452 624417161 179441750 955188630 852677603 423838386 224452416 617295043 297882920 865545159 900941775 279659711 349522278 155611392 780735267 698525086 208211046 946010700 705329981 574300880 953086953 662339171 316239700 240164202 615549016 434971369 580886928 182309609 260724364 359956792 148077719 586117474 848843856 373447938 325698423 153810293 807537930 45496443 287397041 480272377 317160707 801862232 917290797 671170652 287514444 5636249…
Output: 7968816135

Example 2:

Input: 3454 878696343 245985434 448823712 700938507 576321275 717117126 893597429 507593678 293329221 462491270 636941352 145075301 781521295 711130525 929531135 715441503 399801194 608019976 164889397 700384750 600506450 817600643 949613470 856327911 920215141 547267180 859560990 685895553 396033510 242229111 675553454 967977692 203559142 785657677 76350929 153832023 571208379 998661637 96966397 553407808 742268568 927407111 509233118 440990441 956715194 416783125 915330319 609397216 240976841 45536811 454226281 643640332 715587996 453630193 703915167 343416972 881298043 999926436 272375797 922334864 157686197 10887164 346269271 691806889 937340104 522145627 751366594 503476029 375850817 199247079 579140414 713350787 471766592 644048472 676579274 525954880 272599196 849297831 483522209 912895135…
Output: 7634270308

Example 3:

Input: 1320 323836728 462963421 514350956 422048301 621888999 558178222 237850536 826459962 48496392 775574815 589929873 193884391 262596214 779517805 986204240 296135835 966834831 919911106 773206635 506285879 534995414 264681127 499975473 667539225 397381072 240308104 414442709 419047384 784899448 927385478 673908801 395737730 673047848 347980590 11925156 167768712 862226608 177367505 764418060 229407648 483964226 664188639 136835985 613800751 371230835 366939864 221461840 637887183 585378032 815638677 848297304 134143050 660056400 156517790 768073290 293186936 656732827 657706022 730612313 474363281 982271004 308704067 992323563 202410695 146025933 885217320 574080715 52344957 29539635 474510875 632196780 316771579 436679346 763265675 261830659 368733370 444564815 214434081 239027693 167999003…
Output: 9159123165

Constraints:

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

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