CT61071

The Grand Facade of the Timeworn ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the steppe camp of Horselord Plains. Asha spreads the ledgers records across the table and picks up a sharp pencil. 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: 1522 591406496 56543899 566249944 151752220 437438860 83121015 932912736 897550563 38253211 724562588 878076529 587411005 322450485 425947841 542803998 950822631 974273164 253993744 181324857 93623365 602434156 455406594 628756346 533683620 434333294 867976371 343471786 769427293 645026101 197146284 446943235 942572586 904984991 818235001 226229723 686910928 791885195 737170021 828411363 279381663 892153815 990647620 409922953 334822104 54376312 467233029 879927948 892092170 207282545 128594032 729752181 89823946 268809314 504870604 274654730 82918864 566295282 601990531 438530657 268699482 802309054 172908355 293216451 809594340 383719088 629923098 912539555 793346981 633845130 172558113 557299331 346349339 560219099 409783648 68130743 174508023 445297680 640265456 839447979 213393910 756…
Output: 6559430283

Example 2:

Input: 3334 656577243 63216705 967164457 333113839 529262580 6406143 974458416 856283458 802369330 573944944 402940653 264676977 158956422 738214343 297471236 828985261 717680943 458730123 867960392 235441217 630253186 388912237 639523767 523870449 746492881 716094992 325840240 922372428 274549026 46841104 646662055 853837605 5027131 73657452 32121345 710608387 916049969 9709786 120760923 681619680 917630929 93004789 66210251 852534453 338119367 326630868 276953122 984252632 844832074 460823215 694757661 594414401 955899924 469870450 473330001 654126407 181017498 953593377 314818540 575317450 480478 204864995 768919513 984448426 660482676 677513601 187159672 700561644 924936332 299002474 842270635 619189442 397808537 836676290 443670589 929079973 470813958 695764923 371025400 698998501 434161875 …
Output: 12176606390

Example 3:

Input: 1308 839776974 674952717 355583866 758120010 682460317 772832977 769063775 274721290 463135837 179813828 321513927 885133611 744590244 78949786 95288581 419128528 772074989 848866539 13944035 486764626 199205832 640775715 214657659 65722739 254595339 771741669 794779929 374186738 347781329 978336900 344393055 5729919 342207017 510306613 670126939 610711196 169644889 187020027 638473549 650126300 898683905 281349701 118739093 866186828 664684785 888974988 141741785 503904670 146867602 620547712 330562084 411511339 102857640 29125076 471940477 288784750 39105699 119182955 700485307 302106172 774052361 58495273 189162614 806159900 663568994 381022233 478529321 492958259 42663364 678116474 411864534 152552712 616648346 430428201 92215533 914266511 638846006 437227368 802414793 61205414 1824383…
Output: 7477915808

Constraints:

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

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