3032698_ac_171ms_1200k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int sum[50001], w[50001], h[50001];
int inv[50001];
int left[50001], right[50001];

int main()
{
	int n, i, j;
	int Sum, ans;

	while(scanf("%d",&n)==1,n!=-1)
	{
		for(i = 1; i <= n; i++)
		{
			inv[0] = 0;
			scanf("%d%d",&w[i],&h[i]);
			if(i==1)
				inv[i] = w[i];
			else
				inv[i] = inv[i-1]+w[i];
		}
		for(i = 1; i <= n; i++)
		{
			j = i-1;
			while(j && h[i] <= h[j])
				j = left[j]-1;
			left[i] = j+1;
		}
		for(i = n; i > 0; i--)
		{
			j = i+1;
			while(j<=n && h[i] <= h[j])
				j = right[j]+1;
			right[i] = j-1;
		}
		ans = -1;
		for(i = 1; i <= n; i++)
		{
			Sum = h[i]*(inv[right[i]]-inv[left[i]-1]);
			if(Sum > ans)
			{
				ans = Sum;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}