记录编号	118669	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 土地购买	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.407 s
提交时间	2014-09-08 17:29:22	内存使用	1.31 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>

using namespace std;

const long long SIZEN=50001;

struct Node{
	long long l,w;
	bool operator < (Node b) const {
		return l<b.l;
	}
};

deque<Node> vis;
long long n,f[SIZEN]={0};
Node V[SIZEN];

long long F(long long x,long long i){return f[i-1]+vis[x].l*vis[i].w;}
long long CX(long long x){return vis[x].w;}
long long CY(long long x){return x==0? 0:f[x-1];}

bool G(long long a,long long b,long long c)
{
	double x1=CX(b)-CX(a), x2=CX(c)-CX(a);
	double y1=CY(b)-CY(a), y2=CY(c)-CY(a);
	return x1*y2>=x2*y1;
}

struct MNQ{
	deque<long long> S;
	void clf(long long x){
		while(S.size()>1&&F(x,S[0])>=F(x,S[1]))	S.pop_front();
	}
	long long front(long long x){
		clf(x);
		return S.front();
	}
	bool sp(long long x){
		long long back=S.size()-1;
		return G(x,S[back-1],S[back]);
	}
	void clb(long long x){
		while(S.size()>1&&sp(x)) S.pop_back();
	}
	void push_back(long long x){
		clb(x);
		S.push_back(x);
	}
}Q;

void dp(void)
{
	for(int i=1;i<=n;i++)
	{
		Q.push_back(i);
		f[i]=F(i,Q.front(i));
	}
	cout<<f[n]<<endl;
}

void init()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>V[i].l>>V[i].w;
	}
	sort(V,V+n);
	long long nowmax=0;
	for(int i=n-1;i>=0;i--)
	{
		if(V[i].w>nowmax)
		{
			nowmax=V[i].w;
			vis.push_front(V[i]);
		}
	}
	n=vis.size();
	long long temp=vis[0].w;
	vis.push_front((Node){1,1});
}

int main()
{
	freopen("acquire.in","r",stdin);
	freopen("acquire.out","w",stdout);
	init();
	dp();
	
	return 0;
}