POJ2082-Terrible Sets.txt

/**
POJ2082-Terrible Sets
2015-09-12 16:28:15
xuchen
**/
#include "stdio.h"
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 50005;
struct stick{
	int h, w;
};
stick rectangles[N];
int n, ans, pos;
int a, b;

int main()
{
	while(scanf("%d", &n) && n!=-1)
	{
		ans=0; pos=0;
		for(int i=0; i<n; i++)
		{
			scanf("%d %d", &a, &b);
			if(b >= rectangles[pos].h)		
			{
				pos++;
				rectangles[pos].h = b;
				rectangles[pos].w = a;
			}
			else
			{
				int width = 0;
				while(rectangles[pos].h >= b)
				{
					width+=rectangles[pos].w;
					ans = max(ans, rectangles[pos].h * width);
					pos--;
				}
				a+=width;
				pos++;
				rectangles[pos].h=b;
				rectangles[pos].w=a;
			}
		}
		
		int width=0;
		while(pos>0)
		{
			width+=rectangles[pos].w;
			ans = max(ans, rectangles[pos].h*width);
			pos--;
		}
		printf("%d\n", ans);
	}
	return 0;
}