记录编号	581870	评测结果	A
题目名称	3454.[POJ 2559]直方图中最大的矩形	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2023-08-26 16:57:13	内存使用	6.50 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n;
ll a[N],ans;
struct made{
	ll wid,hig;
};
stack<made>st;
void first_(){
	ans = 0;
	while(!st.empty())st.pop();
	memset(a,0,sizeof(a));
}
int main(){
	freopen("histogram.in","r",stdin);
	freopen("histogram.out","w",stdout);
	while(scanf("%d",&n) && n){
		first_();
		for(int i = 1;i <= n;i++)scanf("%lld",&a[i]);
		a[n+1] = 0;
		for(int i = 1;i <= n+1;i++){
			ll width = 0;
			while(!st.empty() && a[i] <= st.top().hig){
				width += st.top().wid;
				ans = max(ans,width*st.top().hig);
				st.pop();
			}
			width++;
			st.push((made){width,a[i]});
		}
		printf("%lld\n",ans);
	}
	
	return 0;
	
}