CT58834

The Lunar Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The registry keeper Ivan has been asked to price the new merchandise line. On the desk lies a long table of ledgers readings. 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: 3667 154052619 226222204 310188524 402850593 301365925 553102029 973868334 808770499 139551890 679886983 231055561 52575072 181693277 8650273 582494201 531881017 601965097 381764973 742541738 572434382 591571087 906695591 383749361 526201123 393328615 503448134 393899727 138659627 245329352 30035311 261152075 140995512 263174411 198812111 505510316 365770982 361387400 219607487 478885932 448509249 483862941 780165585 632050250 370461940 542223692 681478639 225569569 91211628 570002711 160732851 82514875 23826282 859997216 906870175 181752171 275888166 509263143 923138824 236843158 75110010 462592552 899242078 722914805 65046239 961312008 724698909 188038945 791177329 18772085 432877244 456264338 873845849 688666158 245590050 350363845 497366672 722858243 820523458 286150932 174916687 56770…
Output: 7761776507

Example 2:

Input: 3118 123651465 311225543 963449594 30581317 127206464 650712239 511060931 266624492 528061381 842783515 539460110 83779389 585056938 392302426 258272087 17437841 169717781 99314462 272347253 70125169 877574519 769682067 356679190 726201590 444244072 294688433 728522219 937293711 972463235 507330458 672466377 422064577 887086513 638695396 893811643 926803902 551696082 159510414 209894901 610932591 748457305 606781516 88296097 933822941 420441966 708437560 709285462 492238890 340234977 477577460 467241897 85040437 267074212 992755974 544736040 104392150 793982032 572520945 312053297 224581778 407740901 253233409 673030156 491980981 553253720 649048181 830717168 382224228 387550329 124083938 561955353 889833403 221457159 833034994 948028401 574688387 512280453 610587120 966472229 425164280 25…
Output: 8713656468

Example 3:

Input: 3657 511567843 950474347 578498469 976414976 138518232 204324033 676858711 709929735 791481380 185526924 536182989 421775212 61475695 853309319 221611001 566016267 895727509 497912601 816063527 247960447 651870014 837165248 853827411 630089929 320749275 609184502 899259620 556711590 279747515 169916104 697182208 482480370 770153762 710209304 844289340 758448835 78525521 10452044 550849017 987627313 630299218 170672127 855030254 981688438 853314755 907074835 859712039 632212714 918850554 453717741 927311671 815911003 459529473 954022367 855713134 573823355 64867487 863824232 25922846 379466797 177654970 298552848 963721542 150751521 132189208 879787546 802437556 616079868 835782339 38562591 413461807 465120890 216947883 295922959 449262560 316483466 443554473 922304469 61867112 801943720 25…
Output: 8922116385

Constraints:

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

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