CT58938

The marks at Balmcrest

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the cedar groves of Balmcrest, Amara records each marks in a worn leather ledger. The guild wants answers, not guesses. 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: 996 832774384 628670902 515562760 305632211 363412794 713726668 995981495 869354211 406823389 122061572 554699962 238849805 133120482 796528558 783745319 581116660 355049466 162120391 245009971 31486612 296817402 121837721 758833544 971389376 336835367 926426185 753711503 591006008 732001527 248958040 573309715 447090491 548331353 577040141 692507970 378749752 104382895 464507825 259638067 18542064 95055970 749942844 766098176 165613329 747702230 32232924 745342606 953734357 229199047 741258689 921285397 361373838 429004924 454878564 230194903 154110445 821266787 377586284 572221469 45170134 920931542 131525361 399743974 341436879 907194430 923643046 802777907 496030472 301709170 629786520 57371455 245056251 304529714 119725919 104650497 428196337 392336247 935622315 394891966 147559882 75…
Output: 6417010787

Example 2:

Input: 3358 690248492 217533667 383458015 582193099 244140393 170639413 117409209 776140152 409126385 948263716 943338325 138879918 824920036 869925195 954726041 521236950 635816978 17652255 197263360 353308250 932743651 378497198 353489593 509460593 570268012 939220990 331808281 323876641 416421244 775516685 478404616 886897724 84481528 402023035 314104641 83732632 505939313 638308818 572509088 370619823 727176143 323180183 31317174 444704292 959334726 685050262 343865418 159331336 486723196 244343720 700831045 382737124 269550595 736544317 734778965 325101201 863892646 609755929 89814465 517656366 991064484 417536387 277128763 175093948 446548151 348835570 794069627 531349278 618098952 343442069 711488673 904411263 570228709 250375479 193524722 698065103 676470581 267127091 23870669 204666186 6…
Output: 8159981796

Example 3:

Input: 2717 994388692 968406408 926756171 708218760 931548534 543173094 9690445 682838916 828978865 767342026 281198083 922162183 797105171 469240401 542347039 792829031 540605899 698471617 38057586 56171638 896410440 764593195 754931155 856807299 207451501 974434678 512541409 899351183 584531276 44441016 39170490 179626456 146826713 102712840 527893173 961474912 229064498 695550761 894346180 650624698 137610083 511849487 834746243 799729182 282389461 1582925 506324204 148638 439947776 536112732 273005568 935594119 100635 561868002 150192121 157571389 312156163 390749194 358289327 690560608 793993513 980042159 795940174 100425788 504188855 516585749 765970349 784145177 792026619 579539391 153937961 738537064 922533939 724533647 149923525 78430519 826464681 637015693 147372842 328820288 415940433 …
Output: 9193205120

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The marks at Balmcrest - MEDIUM Coding Problem | CodeTikki