1978.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1978 on 2005-12-18 at 21:28:05 */ 
#include <cstdio>

const int MAX = 51200;

class Set {
public:
	int w, h;
	int l, r;
};

inline int max(int, int);

int main()
{
	int n, i;
	Set set[MAX];
	
	set[0].w = 0, set[0].h = -2;
	while(scanf("%d", &n) != EOF && n != -1) {
		int x = 0;
		for(i = 1; i <= n; i++) {
			scanf("%d %d", &set[i].w, &set[i].h);
			x += set[i].w;
			set[i].w = x - set[i].w;
		}
		n += 2;
		set[n-1].w = x, set[n-1].h = -1;
		int best = 0;
		int stack[MAX], top = 0;
		stack[top++] = 0;
		for(i = 1; i < n; i++) {
			while(set[stack[top-1]].h >= set[i].h) {
				int o = stack[--top];
				set[o].r = set[i].w;
				best = max(best, (set[o].r-set[o].l)*set[o].h);
			}
			set[i].l = set[stack[top-1]+1].w;
			stack[top++] = i;
		}
		printf("%d\n", best);
	}
	
	return 0;
}

inline int max(int a, int b)
{
	return a > b ? a : b;
}