NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem58--最大的矩形 [rec]

58: 最大的矩形 [rec]

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 18  Solved: 9
[Submit] [Status] [Web Board] [Creator:]

Description

经过精心的计算,卡卡西终于帮助白胡子和黑胡子两位巫师分出了胜负,他们也遵守承诺打开了锁链。最终,卡卡西在四又四分之三号站台登上“和谐号”魔法快车,来到了世界魔法大学的门口。但此时她却惊讶地发现魔法大学被石头紧紧的裹住,转了一圈也没有发现大门,这是怎么回事呢?

原来,大学门口有一个很大的广场,而广场的顶部有着大小不一的长方形透光栅格,这些格子沿着屋顶的一侧整齐的排列着,它们的底部宽度一样,但是高度随着阳光照射的角度不同而时刻变化着,并在地上投影出变化着的影子,而这些影子所组成的直方图里面的最大矩形就是变化着的学校的大门-阴影之门,你能帮助卡卡西找出阴影之门的变化规律,准确说出阴影大门的面积,从而进入魔法学校么?

在横轴上放了n个相邻的矩形,每个矩形的宽度是w(所有矩形宽度一致),而第i(1 ≤ i ≤ n)个矩形的高度是hi。这n个矩形构成了一个直方图。例如,下图中六个矩形的高度就分别是4, 2, 6, 5, 1, 7。宽度w=2。


请找出能放在给定直方图里面积最大的矩形,它的边要与坐标轴平行。对于上面给出的例子,最大矩形为下图所示的红色部分部分,面积是20。


Input

输入数据共两行,第一行包含两个正整数n和w(空格隔开),分别表示矩形的数量和矩形的宽度。第二行包含n 个整数h1, h2, … , hn,相邻的数之间由空格分隔,hi是第i个矩形的高度。

Output

一个正整数,表示给定直方图内的最大矩形的面积。

Sample Input Copy

6 2
4 2 6 5 1 7

Sample Output Copy

20

HINT

数据范围: 1 <= n <= 1000,1 <= hi <= 10000,1 <= w<= 100。

Source/Category