变形金刚

Time Limit: 3000 MS

Memory Limit: 32768 K

Total Submit: 27(8 users)

Total Accepted: 6(6 users)

Rating:

Special Judge: No

Description

新一轮变形金刚来袭，这次霸天虎的头领叫做吊炸天。吊炸天有一个酷炫的攻击技能，能够横向摧毁一个矩形区域内的高楼大厦。但是有个弱点，这个矩形区域必须充满建筑物（不能有空白）。现在吊炸天面对一座城市，假设建筑物都是紧密挨着的（没有缝隙），现在按照顺序给你一些建筑物的宽和高（二维）。这样的话...吊炸天一次性能摧毁的最大建筑面积是多少？（不考虑区域外造成的损坏）

Input

多组测试数据：

每组数据的第一行是一个整数n，表示建筑物的数目；

接下来的n行，每行有两个整数 w,h，分别表示对应建筑物的宽和高。

(1<= T <= 50, 1 <= n <= 50000,0<=总面积<=10^9)

如果n等于0 则结束。

Output

对于每组数据，输出能一次性摧毁的最大面积。

Sample Input

3 4

1 3

3 4

1 2

3 4

Sample Output

Source

2014暑假集训练习赛（8月6日）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
using namespace std;
typedef long  LL;
struct node
{
    int height,width;
    LL left,right;
    int l,r;
} a[50001];
LL max(LL x,LL y)
{
    return x>=y? x:y;
}
int main()
{
    int n;
    while(~scanf("%d",&n),n)
    {
        int i;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].width,&a[i].height);
            a[i].left=a[i].width;
            a[i].right=a[i].width;
            a[i].l=i;
            a[i].r=i;
        }
        a[0].height=-1;
        a[n+1].height=-1;
        for(i=1;i<=n;i++)
        {
            while(a[i].height<=a[a[i].l-1].height)
            {            
                a[i].left+=a[a[i].l-1].left;
                a[i].l=a[a[i].l-1].l;
            }
        }
        for(i=n;i>=1;i--)
        {
            while(a[i].height<=a[a[i].r+1].height)
            {
                a[i].right+=a[a[i].r+1].right;
                a[i].r=a[a[i].r+1].r;
            }
        }
        LL m=0;
        for(i=1;i<=n;i++)
        {
            m=max(m,(a[i].left+a[i].right-a[i].width)*a[i].height);
        }
        printf("%lld
",m);
    }
    return 0;
}