CT62536

Crimson marks Grand Facade

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the honeycomb cliffs of Beeswick, someone must fulfill a tricky customer order. This year the task falls to Kavya, armed only with the marks register. 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: 882 69533288 542054247 826832390 230921688 1548689 167493043 797680407 474565917 367429547 167084613 788545780 431853922 692058577 27555575 509968208 275481362 200157410 171038437 230776555 844800078 861693681 569724445 20259311 998008817 690638995 412735650 899338228 191643042 538847133 981532239 858034548 13833250 605618494 717190730 398595980 50706481 149121517 518207424 755082345 314733134 985714610 246239329 158047676 747280847 652473283 131046237 854716757 35639706 629426641 596305316 993786875 510026576 228991585 149765140 626310148 173314724 679983371 810251181 894986701 301737933 920595810 515989732 861307052 343309235 479299730 967036328 387693265 544174108 905662826 98906496 27843681 183173753 5379219 962558967 446553335 81429814 556212044 816834959 89803636 577486431 81479751 7…
Output: 6187758297

Example 2:

Input: 2888 545132904 647258410 635167762 178394535 250692264 368697517 150872062 516707755 991375033 604597084 30654466 578831492 301473994 69316473 37914302 23830538 585367157 863080588 704883794 91209240 349248430 930490702 169406094 272770166 669414475 470850596 361452018 969259107 375448224 75219540 214743438 373928136 196248651 260233269 726935274 663989332 691314682 215379060 165100313 744582717 207254471 351618988 694746969 902309692 324834646 791842205 682180482 325442794 509706387 193300636 447628077 789718630 548341104 454015458 669507073 361694580 752993412 158130480 703908070 708216940 776286581 277516926 274154385 40550013 452596656 165198775 528274427 24103545 852745551 909433328 887770217 126546313 194377 244136045 59765130 641112525 721586045 776867422 858227561 553963177 6149906…
Output: 9732361220

Example 3:

Input: 3006 567777156 829274716 603856031 140711489 536432711 191427261 928984783 975904431 185559410 456584289 518409728 377736976 434361993 190632399 988935373 160642463 101620459 972791474 794428460 780477410 307990709 773600675 402901910 341743282 878670560 284558267 854783768 524083924 517534054 321053201 482712021 261378017 717839675 496270874 836948348 6371753 663647075 189512927 974696345 460126790 185810490 182261616 291576643 50958866 60306322 814236909 40818031 593211431 950175995 216527372 709004024 800826739 970394697 999788141 284025049 210090690 858346535 20043526 139176025 105458303 211373207 386483945 346499483 629772630 516545859 640039979 426337420 971825004 795782364 467413021 707808928 372601021 489954776 67859357 165591319 436016037 79207963 868352545 526320509 926465663 958…
Output: 8110993665

Constraints:

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

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