CT65217

The Wayward beacons of Kabir

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Kabir runs the apothecary at the railway depot of Cinderline. Today the books show a list of beacons, and the numbers must be worked out before sundown. 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: 2566 249009916 645282694 96868704 480132264 192346127 157281992 857437032 596759681 30007146 608085603 20202757 176241186 667931253 51247533 962351961 600273605 184461959 204720010 481151906 999024951 359796022 738776969 859768158 675360781 320815572 811572232 701820937 128522614 295520496 435793409 182834040 172968379 241277619 792735125 818486752 112789496 627531871 296859796 69172369 514901559 653520544 118076786 83274493 358550421 428145807 601270565 251325063 787080709 242095284 5403932 204792989 248547741 621881743 564627803 830550091 75626268 544428842 80908613 708209081 329816022 701693014 290896173 553042868 537720476 756832126 707411019 65310296 786780689 515455093 6897181 594207149 283751257 332321922 880662549 572212726 639302542 454373278 235009436 594436800 200911933 40434755…
Output: 8427859425

Example 2:

Input: 3528 827044006 264689550 123926824 169341706 535356371 338324319 824908385 39740833 354775534 879054739 498256147 372051080 155065288 599851318 661261072 58865185 843138640 123353522 611168817 458433381 516226904 420475482 863862524 160096532 298155295 656820459 167530185 689991709 768134048 589280385 689928510 897332873 802603223 298586438 970870760 480150386 903900853 21979219 395851904 566494722 497408385 592720819 749092040 161291319 998732354 288114128 646082175 347507109 789868234 547378088 933722652 990839889 248138125 144987705 941281236 48139425 501736768 268987118 805795946 908515545 459633630 553615128 357353310 687608332 804272514 640079234 768780440 358122819 220768054 150457834 877040778 544933383 33343907 645740251 248863131 802678690 375498315 527868462 479634643 229255428 …
Output: 7952864088

Example 3:

Input: 580 823700434 160935210 623250629 687898996 505315270 116775522 647544079 175528970 27569411 912041895 808023686 667092321 941611666 722859104 26260759 125065407 265307881 673494943 585541135 930141725 768809550 785891212 397915213 610345257 515920716 738762572 41760439 797525035 90497228 518725210 702184805 498681247 369559974 840352025 348756619 388442571 57803096 441332019 104313979 102190067 141570743 382290560 752954988 272001364 223114610 511739755 409285670 436077181 124045581 549250073 369184226 447333316 326549024 828455478 12481767 101320565 78222411 195196767 384145134 365988386 629904128 793498860 643340938 105615423 705949961 152016485 783931802 934100921 287498630 877914065 30082608 810318571 86973439 466072368 915879992 222050803 318652484 885508549 656510664 891826224 25743…
Output: 4925936687

Constraints:

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

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