CT57916

The Grand Facade at Thimblewick

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Bhanu found an old ledger of registers in the customs house attic at the wren hedges of Thimblewick. The margin notes pose a precise question. 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: 3099 752038356 409433615 924425399 680618258 661597687 367872104 172664873 243204373 898718424 409066053 838740541 627622170 721961705 768481213 852355571 528027547 233047114 548909748 465290617 50080836 810076388 573348629 194755692 103777348 403191470 916718700 58274877 978162321 942447005 927544729 481184439 619082067 311412145 509235324 583583110 214587332 273890319 421924929 358675535 579866876 975192496 428727689 655000638 378286619 133002835 757443170 131536769 721788654 368058462 792340672 500186987 533512626 538742412 993034316 193150754 539383060 308971938 647388399 725241506 403140443 92297942 576010325 944284881 551910871 298955724 77402380 377219221 737688703 118710802 88919290 292366433 762274694 323575907 266686752 882836223 986587320 536620664 944054443 420596612 568822009 …
Output: 7702532376

Example 2:

Input: 3031 746486253 98838115 557353590 320589277 24763579 460609602 758472014 787694414 928182346 688955296 541334193 138536769 147280517 983252108 790464642 270596545 224881387 768619483 149826289 931785366 463044445 623461616 725346726 388404644 532766459 906448705 815226407 800108811 926244261 614018134 905772218 433165218 326439570 336144631 243824438 737032972 963025749 32626210 568036768 301495212 562326728 128463677 137594869 275857811 568633707 249168652 891223926 833382990 880062260 747137212 449106142 712675432 238330216 739710733 840686006 507412905 424275019 481465402 399424386 346991276 306101878 89914550 688534019 540050292 764371540 380250090 437272409 522903063 393058892 154516892 136685661 182689546 317522326 177190099 711547950 992789242 627707496 344598916 124079161 962336767…
Output: 8443482957

Example 3:

Input: 3448 763117341 134606770 448889782 169255941 885252530 532909389 310868860 103160326 420997861 765287077 221013226 499497157 755427384 465427211 635579099 30628724 190112948 276195423 886747868 3477292 583589916 290931193 485552554 649015475 280746963 443010644 138026570 106414865 164297414 142356562 139040156 321661869 124939497 331742461 236572788 899381299 81958011 884660704 634791170 123351706 925351445 618649000 191316443 103045723 673912297 590327466 279114485 894447966 929315554 84265699 356002090 652729144 595883113 444220910 25820152 200173189 91341361 420037088 86468872 413370746 739824999 721229773 899926825 135777073 163603180 139877063 906769422 593794734 454164603 145656726 778524309 665630030 428665375 489164149 897311090 738770252 250469462 531399508 815793954 841178540 285…
Output: 9707703872

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Grand Facade at Thimblewick - MEDIUM Coding Problem | CodeTikki