CT65116

Orin's Faded beacons

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the mountain city of Highreach, Orin records each beacons 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: 3276 789847091 28754663 227540771 245049601 842500166 186187724 818943794 101244942 245601742 794490651 384804450 319939881 280740606 135391065 603091244 693251067 223210565 852860789 870610941 433987924 123052851 472444917 909564480 234211497 673994633 567652291 682091746 723614914 702526912 643610887 819673621 566472150 805969620 491706561 340989212 458196860 410937996 315644288 872868092 304948645 437987206 246602275 100663498 408306146 112178091 253233611 537437828 684026770 896573309 284575546 601927819 288310021 746578058 658803243 547623572 118642920 662736368 758861218 467714602 383054037 450374588 118301693 869535853 165164331 683759866 508577970 374650737 465317474 929482742 926997052 150068959 391894673 958344475 955383376 461965225 27245478 145247015 702830685 829577235 5910702…
Output: 7348435354

Example 2:

Input: 3026 561266726 526698745 798667870 317533233 405224371 981029418 774857115 654619461 960659205 603431657 388332025 919324304 622435016 257057327 836821504 518138698 250428976 470808929 362575459 571131488 564394504 226203890 540563371 466832758 893228541 55475652 106314473 238784155 533149008 673102308 842127804 873178373 103836555 854715709 73674576 52556970 255391616 853260702 18260859 889628688 918259559 355170411 472422488 854549160 58771076 997255498 498734839 203317008 944644067 84907408 570127120 968839995 816002851 736942900 65362743 630436171 686021424 301484582 888338732 26192147 770671653 423145150 377903552 908446548 631796293 429021257 170629457 674584980 513159521 26038230 166919937 342542088 298272682 354464514 843455862 415408179 469915263 5190352 392196735 71198873 3550128…
Output: 8489787856

Example 3:

Input: 2833 891040037 618444834 818737819 502539109 284443627 794539855 725092477 429596730 315575521 760452668 642789023 602359796 609616708 226888456 209366580 747513824 536645873 862444340 758847155 526444036 719880756 549936941 423510565 127432740 811695733 699090581 559758555 767142862 982157587 206536245 97520660 507074942 150715252 505655190 964924119 408862493 366468115 296199273 20730884 864089878 545908393 344263232 757699577 62617545 835721314 392403839 674002677 707724904 574019094 540861240 687306483 293424417 291119790 214590549 425893348 957779557 942955741 432373626 168088175 914602473 537203337 247861898 722947408 953112604 65960377 680481440 88342607 516466560 29826251 340264814 465557617 442346844 770526864 824615690 18424750 96554052 645020750 454064966 294634178 756684505 888…
Output: 7575630478

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Orin's Faded beacons - MEDIUM Coding Problem | CodeTikki