CT59360

Maya's Azure Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the ivy courts of Vineward. Maya spreads the registers records across the table and picks up a sharp pencil. 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: 675 304892456 886447304 206679198 722778183 893370277 589402000 295207669 170044741 304820864 604974289 153131664 307929725 757163169 816083757 710620277 562316283 261643213 422616049 232079078 94963999 717545973 889377402 2841758 412376576 824786315 83280909 281710546 509697184 301920495 462697834 168252458 614144047 277591251 65236722 571789755 640938247 609291212 362823660 531867532 37191006 599989956 121855676 919995564 630686504 494063135 974555639 863402894 485441649 75311869 568324293 795650706 950596023 673410787 82461388 549456473 51651624 987323609 385032432 536499440 631934311 58848299 580332371 850112118 414477436 960948980 616315333 498671998 50915041 386769194 149295519 114818706 310813713 161801515 66379032 328771305 612685441 983840312 896630054 160226300 898458471 14815289…
Output: 9935732640

Example 2:

Input: 523 6036309 265493542 861477634 117823122 888368214 659910726 498669067 76871891 354818698 797471726 218814598 935944994 270381427 128461211 822678668 255477815 133999703 34232074 247844974 258835898 378761394 703793874 312402453 820271110 208620668 927072476 131523654 551974692 317764134 132011519 616009812 253311599 90261992 37603959 524116435 769971433 53873996 842776767 350541231 15664895 24595978 530851216 803143201 789058421 290068275 95050950 886124065 467545471 314188419 325725940 681633882 412683167 186049694 385368557 389750779 169522506 400463860 946814845 151456862 285925465 14899754 323886245 453489850 641567047 200987895 221456245 182029385 145149182 57283281 528953527 95920067 903039352 109150940 404925996 498262349 848256133 36295202 82626140 173280336 626537281 180843847 9…
Output: 5859084478

Example 3:

Input: 250 22935126 393728413 300600821 451503767 251675145 599349890 617442058 427158679 28342689 875522882 567700079 749582502 787000271 991874236 501634255 165638942 604300792 69265945 817399955 847866406 523559746 318198352 323640757 332336630 885279629 51311839 286259216 109380354 391257573 871677440 830125811 857264280 510243975 46934075 311861024 619408718 696753914 913326766 859504416 498258785 314982731 65339542 808278194 340737388 603229107 302048304 338122975 741170001 764392827 85484187 662758656 364443071 444087274 258127595 267541690 40055690 204321367 865702829 221296627 755143312 220213161 192186584 862901288 662847515 519741162 593549733 909671854 435809495 630068282 936973945 390575812 307237216 707266780 445663770 338423877 788725485 433127797 110867097 522455700 968355962 4517…
Output: 6378205214

Constraints:

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

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