CT59072

The registers at Padmore

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the lily shoals of Padmore close for winter, Gardener must finish the registers ledger - one figure at a time. 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: 2293 730857439 777410582 830977479 73805654 62372161 980534799 263472430 718000496 15761122 193023699 922014586 404584048 223495400 46995229 98932332 943873824 442351676 400443190 294554676 56258727 655473321 739069004 736446680 419807078 810126113 91446013 729145572 846186714 679272925 738636258 370418514 260001888 14079678 466901311 513128860 15547911 443003468 977290544 562385548 394786409 979585854 45381990 722467228 336149185 606133036 257957122 829447002 234164939 245416340 272734294 700029837 328161999 908202162 256068271 438247932 743236684 318698919 337767912 206173445 536255185 238306399 235683668 643696486 481197780 837503857 589196243 942125080 490974672 423206236 202646625 227669918 433722018 126205868 22718634 959077960 803954086 979144260 700492318 740214229 647537525 233870…
Output: 7704573952

Example 2:

Input: 913 798826177 623694331 266093236 380440281 371839273 637014030 754894273 32966921 1349172 545847357 922334068 634741574 848262198 904431690 73090353 176260310 772683965 281795921 977258905 266198446 324125193 974590715 968736874 619284590 226313815 69701541 476559470 344501062 884562592 991636294 595617270 48269436 620425559 844516136 700466654 41695106 304126007 65645064 779296367 868896673 40138709 605597542 273932649 459339413 657212789 316488056 122289579 911464408 15608283 272087433 211794574 352120785 96863402 95139786 686101293 37999027 708484385 931472063 897877581 277231785 420826219 553213225 939252731 993879394 599530120 621856049 860463712 292562654 960212959 647088817 193352997 673444398 472484397 302770411 476907288 274525018 633072780 673061852 263234849 469963090 928866335…
Output: 6923068380

Example 3:

Input: 3300 326486595 6469055 865243360 859294637 3754637 1704267 732275709 841543092 425973984 552193156 321172815 619320400 189789064 974689800 121554483 684094738 112757431 288705513 331693470 242645166 139652392 425928896 274486512 203648374 154476242 599985817 545358820 131910861 894063921 29502375 236145769 444919974 52538792 900559319 266235983 310333545 212276172 54239899 952546706 611060904 443910810 865596205 154878823 242302732 998898988 946686065 16802274 311874988 726401844 693647771 321562670 552839412 544472493 767787981 468184351 80800391 46463507 23055544 348286285 699069190 415401607 409048208 212582888 629345457 707618688 784717755 706386888 861131803 44594379 181962985 104917272 800653364 518666451 592710177 339649525 664893179 490268593 218482533 789282528 166024070 350149531…
Output: 8526419564

Constraints:

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

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