CT63660

The Grand Facade of Gusthaven

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the windmill fields of Gusthaven, someone must rebuild the damaged itinerary. This year the task falls to Cora, armed only with the ledgers 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: 941 958298631 926997600 281429367 866592650 948209196 117893323 431556168 220119612 60950926 67627509 515128075 688383569 811892711 972179159 222890406 732432004 178102538 289143251 667433923 622073452 329951805 158649121 368957126 980358691 710710343 113655255 11870315 548672324 160182540 764487002 952213136 362412117 35221645 124584249 398981982 506696455 188404067 735271424 174755710 613504327 413961743 941687663 381444789 998144761 68555945 305341812 609447613 919436988 326839349 349817967 113772245 3226539 939381038 54745011 415384350 859771278 147414348 109401634 74215430 889303365 748006113 24816592 651405577 404899266 723855952 194228371 662584172 784577150 284805348 615719461 651859910 569612511 437343846 653419923 222881663 863313762 355847397 231254583 92458381 650649839 4763611…
Output: 8225985200

Example 2:

Input: 662 772230607 218075994 28156969 134235016 727070166 599108766 491540330 510459600 665992648 776808804 153977670 367658146 791971515 732911427 818202302 118158057 285873235 621713206 289975663 158662508 914757333 337410883 696571396 667560180 764574229 594457317 415741749 439557988 698061784 647958057 676625199 522188569 307099601 554998488 854975707 783283568 584476348 8414110 45387450 276225306 954941894 535114149 41483066 39224264 140655305 321336715 600135619 894412165 14600518 617542687 393683204 924848877 387077788 356493092 805223142 438063544 120053054 745430518 7089041 585869050 463708570 253697540 828365872 647132328 340443639 334774201 887948280 662689841 648655283 627514733 771469508 733540174 162137660 56960533 889419525 679126753 706898427 527009383 298919043 157134393 713296…
Output: 5358368972

Example 3:

Input: 2286 911662906 680238682 18669767 781444841 770747755 858460687 762908512 394900832 759052374 660507732 591316364 122898802 218277776 968565990 227032544 841835989 4041685 379890642 929682205 829003850 788968003 542332364 84298932 93500231 27897662 465735826 717969838 412547543 918411767 58915751 402943015 776142448 612573178 982163339 886632556 895955306 147883379 574460104 59828228 279293010 257027311 252525011 788050608 129320155 285727890 136298832 200454688 92088956 705301295 766530929 986373868 28979557 114255907 523801153 955832113 539651833 406816847 663999628 736494929 338773363 122494884 746352185 233231291 854018958 333740662 156361146 972132832 646639195 486752994 399033812 915390378 572007820 139708624 402473416 759451485 392131694 94538498 394458631 328482538 262169947 325153…
Output: 8101164045

Constraints:

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

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