CT59256

The Grand Facade at Saprun

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Uma the factor watches over the maple sugarbush of Saprun's stores of signals. A careful computation stands between order and chaos. 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: 574 518331221 279357657 379615787 807702569 474591064 632772521 999544834 752967377 390276895 17634644 557598506 907545647 249574366 535238244 513432366 723219969 681170717 651946333 646431093 657472213 715252369 970549443 379325391 655113130 914016326 535542383 958389533 512868071 759165748 775241492 227949702 591556072 190985380 185987812 348934598 8578064 761565854 340074317 489596560 2338066 297952804 622522969 684813853 16710046 300416317 563927042 900875015 93916575 667193252 253482886 652974824 36184391 716176559 34228687 902063714 889161309 571836227 874776924 258014059 475687684 501099763 984424580 900486857 701887290 324354265 860187189 520136774 411549864 315674242 797082958 265785628 15843307 498065725 733810524 86511568 892472824 339901871 966168374 653386994 452309485 7130239…
Output: 6448531647

Example 2:

Input: 2488 265313323 616855699 42917037 202705591 929221967 603624506 549499290 577779307 182055408 738982909 114824245 302773317 385981760 182881947 763374868 827746535 575243810 941316245 393615790 497442993 857653562 548064164 812086135 142290876 757144493 189021897 57737507 647498162 124707725 992678189 647254780 360994888 896068307 685777015 510628935 853720918 552063300 896185856 433978167 768022142 549868689 891792925 726167303 997587168 566420394 159146086 844903192 344470350 779397344 654307482 78887488 383185752 8051221 291044876 890163135 678883361 999934131 933775346 30365715 603432432 885692859 17172644 22426246 830381083 652908633 603738519 982828473 139917584 219645271 378156428 617373319 705963826 692531426 109784642 595130556 260622056 804178380 825366308 992752653 334085599 938…
Output: 7484613675

Example 3:

Input: 27 139307915 965179055 32322527 10495105 62627208 485919469 256318516 120068739 756759968 777833439 759391765 876896651 915357791 793864747 3715311 385010030 338190705 882073642 255763097 977707086 287830595 687082761 587438235 41091423 580393172 889013937 25340042
Output: 4540559808

Constraints:

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

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