CT61467

The registers at Brineport

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the smokehouses of Brineport, Minstrel the factor keeps careful count of the registers. Track down a clerical error, every figure matters. 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: 3518 520854306 538504097 297514536 12484108 477682765 529928112 129485825 259652924 43539499 326939139 20550894 940775334 614674871 918868778 96754724 439210921 868879454 385224799 243599384 504460347 311316940 723292936 999477940 880337335 653468120 826652614 294304036 612630831 970075005 519317032 420737533 410260206 837502900 259585577 548485368 64679115 468677250 98430762 829060331 651121656 737680626 562983198 669242013 321832668 820626804 952310661 115598777 120665652 374303753 165652607 164129955 790672158 479610042 73010880 554651774 439332580 396920068 108112262 245363105 168100822 398941439 602335323 353882748 982630041 99582136 314626736 52350947 533635540 449580732 54437600 141097228 674216697 992125413 756195527 186979861 627774141 472743983 170035492 104983591 634364534 27196…
Output: 11769740304

Example 2:

Input: 1860 735100060 974491837 526954561 16208947 37301210 17438471 897510755 47683944 315677941 674061122 58248960 758958811 817460546 568899608 174493688 197350908 674938173 542239193 116914059 461586074 169585179 252324683 1154839 741764317 56890012 982316608 496084073 218550816 185277860 583845138 454202404 387166985 946805768 601892094 777648837 620697368 260936117 556022887 384130219 427785538 537046790 146475697 15183083 364976628 488870576 951568704 222892918 759393344 792441865 383837655 764447709 874897048 535750415 360190886 674288307 327424677 30484099 838425421 861412294 875057236 683995298 901630443 313854760 432040539 392367280 2718226 342138099 77286239 186774069 279850823 500212996 759172878 917453195 984783819 821313256 347382746 472946980 927402804 205714124 594342669 77948629…
Output: 6933797820

Example 3:

Input: 2037 457973385 385626778 985705564 865252519 256143254 369966189 79745378 431010750 771814804 216542474 794598841 60952926 819381984 809953925 546905079 396472593 768423189 909695678 664178399 143037010 536547225 9094063 430206228 56779042 110186107 84619711 293255948 620543287 682530324 77490969 501373468 164117463 315019254 543318019 959193567 796996037 182606804 479949000 409786855 290916155 863925295 258030055 172970384 888749168 444526317 717113313 15004205 715003156 335722577 968612700 642404071 129450711 57310002 767508187 177877372 509036009 346734886 767826945 304925410 564257753 487694847 190486623 752450477 764075408 287679535 233859838 250647757 948175209 969254659 723062951 861571652 323564215 571923499 52474706 726517201 4658721 531058439 292384093 499029376 453349507 8407463…
Output: 10235266245

Constraints:

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

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