CT62745

Faye's Ledger of marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Faye runs the timber yard at the quartz ridge of Glimmerfell. Today the books show a list of marks, and the numbers must be worked out before sundown. 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: 2484 857654888 437985585 674782532 501952551 894606692 206686874 771076008 708716937 19400026 246889269 25271990 605596129 597453607 625751417 463596358 50987621 502530802 931218620 373159044 601311241 765370873 564140796 974924850 538988466 688153160 335350355 692047580 147949864 210274864 308603417 569301843 32705375 898182730 99908593 387481288 25928630 93307432 194891157 920127787 56265024 993707073 486313496 129792474 162428979 465839036 139083947 565203885 314742048 913656962 965388496 674287779 108985653 785606905 900737282 614400166 739468533 967823557 179812711 612141899 338935069 584197133 349809096 615348029 803643461 470257881 599608198 822209875 434444501 803656171 333336287 497541214 139284212 722659597 953942040 189218662 891673981 233427440 421838019 200001497 736604876 787…
Output: 9653959184

Example 2:

Input: 3658 56306783 465299468 529004856 6879801 163122651 470020160 874627783 71965849 5456020 81404165 4459721 334015737 128220423 447632429 435663882 901096378 48400619 551583415 543089370 596860026 226829130 646570840 152960520 787244597 288147960 543583597 400995539 712344314 562598796 49972562 358938928 309952761 967020959 245998424 761474818 617285944 55389371 33609501 535016256 789613818 625758966 572085322 620532492 658862834 27349266 985644083 351966188 778639203 613376182 747558657 526471691 771244384 989966549 900405585 166941345 686587569 737219511 614814944 772850925 872957552 976377731 629103806 675609473 170969392 153424924 232209541 37492902 488647967 422544942 837067250 399313165 16619384 766340576 337307926 935479037 491749520 775194765 827929919 584507222 953618094 349345082 9…
Output: 7651093688

Example 3:

Input: 3607 755895664 638909086 750529972 399952317 998677116 585013686 474351687 286578121 488000686 447667015 962632106 404134350 320737998 427883515 597388479 802783612 795380644 600092314 92084928 201336600 864622051 760440351 961997959 861996507 571177219 765329006 77706965 35070688 7973531 134202118 776253932 417446402 470687789 417993748 685887074 40560602 993252733 816562555 233942761 680785274 27655460 728457419 37480907 851529608 302243738 861825443 862040658 743733097 941617344 242035515 18810913 419253884 214187274 642137651 592789205 566943433 719565301 781884481 710937435 439125309 660754539 459722654 785220718 876781503 5252684 641445198 334562284 714254873 741112429 422978089 78002174 828008660 734568942 719972964 208739870 464330635 992848473 757600960 362630926 749140023 9059653…
Output: 7479248128

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Faye's Ledger of marks - MEDIUM Coding Problem | CodeTikki