CT64261

The registers at Balmcrest

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the cedar groves of Balmcrest. Tara spreads the registers 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: 2273 355779593 371666535 537565883 669921686 876969677 825889205 634728107 420397444 875915746 786033387 374137872 473039754 357064120 563907909 176388358 627868701 888494458 715905270 698964426 513596092 138412410 498297930 784057480 829028508 913837934 435520248 384859934 841842346 142892152 582339292 897078844 206598385 228370628 750596516 93361851 991770345 184558353 230373260 94989547 705015700 709332346 886961208 222208420 195459743 317499588 283943083 979801597 215105775 235072341 681067796 329547618 558478367 515927024 692645059 635978068 645101884 171131055 428419767 837877276 891465611 733939813 866332979 358862539 579977925 21069888 425159226 606659530 113185007 648404549 939058408 812023786 952449504 423008205 400173310 963312732 990076698 196944474 62985944 277872704 989267616…
Output: 7845706272

Example 2:

Input: 1367 299892044 366122362 150925204 438806207 775352395 761441714 25590265 573113665 362180933 622324146 222476000 269629479 63904055 147810313 107412932 553305737 982577996 695948731 192352016 211556241 982792751 337408494 720446547 121745941 484426908 38618577 949222646 335849546 753735282 973641450 160176203 88557505 844832021 716556024 802068627 388669111 745501673 591491792 420375433 140481263 670313622 994981226 968390531 606830489 317597333 550788720 405633030 482224522 632011799 487817942 923819905 850404513 460243156 787802333 769979877 635546534 265560191 690838737 713478363 378539654 35220941 723091932 799499252 377341393 18928715 105152351 140315148 148726853 548488877 767326349 104623703 463486054 326189353 246327130 802613822 439978293 428217372 573300146 621124518 768931608 7…
Output: 6941648952

Example 3:

Input: 497 52801702 773956415 193565982 318704462 884389330 724582156 513935300 893821083 403490990 605664930 82406412 839618789 327239699 302912965 196702539 631647381 599934501 876412641 299612391 561135660 747610668 645411014 307696545 804908416 211606184 967712165 807774110 439585777 725910039 981910388 375853146 45833982 189430788 30216479 225574128 536010303 441541573 898234610 323969549 221553543 922606002 944459210 602675163 639877209 75279363 223102961 150409531 997841478 127220069 935488234 942521134 513512081 215201442 469401779 711318764 87845653 374037912 60265526 990188062 27489310 351875584 14263539 307432409 432025247 153945778 94516486 723161247 114630722 456841742 709542728 916517433 961708480 79294507 446812344 360121353 245451883 832551323 520896290 709171460 404060529 4422672…
Output: 5983632642

Constraints:

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

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