CT61496

Baron's Zigzag Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The council of the tundra station of Whitesnow pays by the answer, and Baron intends to earn it. First: the full register of ledgers. 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: 2689 872263684 521944962 339732896 775030769 316936175 515254613 897997645 85256931 906749115 797663031 98884523 849405424 955803013 240885515 830298057 948927710 926740298 852426999 721730197 79825262 958613583 412153010 667224519 672955312 816743165 26525634 98175726 65628785 190735435 947685629 381950640 650736992 584002436 745677037 527211176 337670564 167054993 305481729 892539080 472180144 449738923 969393057 814984060 861281028 213905854 948086728 676495713 538861379 694937522 282148539 140095602 456675477 655467187 740637162 556479533 474942187 399494709 200551610 581352589 485704572 183385216 439021217 388649276 272971040 494540286 806713688 50060735 328650449 673615439 661394339 46661934 781957893 669660006 259761355 9288690 911909126 120574890 2374380 144567727 667765587 9468274…
Output: 9307136808

Example 2:

Input: 818 851454857 566617423 102758373 181274510 750715292 29491657 711291793 75770266 802613821 801545223 434888924 231763428 722730730 206983011 661176275 578011877 516484068 774488712 90370235 635336105 178350031 244067195 70259019 576673027 353267850 199842229 760980320 581022692 96088502 830671641 806195943 150629667 772178550 7259149 774402739 399968685 414691334 344307241 959796058 880600378 899842342 397906114 673999481 529952443 55534999 754205955 824275089 696210566 110616405 20968070 643117722 97734863 171284797 570848774 190805211 873041756 322834159 806657040 9906409 802399383 150597531 205167780 886320745 121959986 426958177 572645852 499023570 172292391 550095254 268810121 990040189 412838974 881772792 523809864 946000452 684496734 700709161 75443789 149321638 799929479 875289096…
Output: 7353894555

Example 3:

Input: 3365 475337067 397049303 428003404 748142738 319592382 379011149 830804098 342250011 833499554 462044946 283459390 240876357 658900573 971441097 516206456 998120835 560945848 229708829 705836199 425639604 278651156 103937527 6092046 342548014 287723405 479042173 633861852 964927624 601533789 717523597 146854232 821180234 226327526 692519509 446452515 93072100 248926186 593499960 816303356 683112005 880189986 430548820 590258398 684610803 687176376 660905828 812103507 446397875 495469393 366245490 602759264 601023708 143432704 285073993 509242487 242429904 858171124 845056773 178418357 352076372 240701097 77854289 146025459 419268072 911767036 261183310 103509480 614116656 656284904 430625051 432201552 132274713 825820978 969718185 845595573 156129270 88716815 646927780 379570546 613041571 …
Output: 7834659742

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Baron's Zigzag Ledger - MEDIUM Coding Problem | CodeTikki