记录编号	62177	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 土地购买	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.205 s
提交时间	2013-06-21 14:37:17	内存使用	1.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
#include<fstream>
using namespace std;
typedef long long ll;
const ll SIZEN=50001;
class LAND{
public:
	ll l,w;//长和宽
};
bool operator < (LAND a,LAND b){
	return a.l<b.l;
}
deque<LAND> lis;//最终的土地
ll n;
LAND il[SIZEN];
ll f[SIZEN]={0};
ll fig(ll x,ll i){
	return f[i-1]+lis[x].l*lis[i].w;
}
ll CX(ll x){
	return lis[x].w;
}
ll CY(ll x){
	if(x==0) return 0;
	return f[x-1];
}
bool uper(ll a,ll b,ll c){//返回:c是否位于ab上方
	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;
}
class MNQ{
public:
	deque<ll> S;
	void clf(ll x){
		while(S.size()>1&&fig(x,S[0])>=fig(x,S[1]))	S.pop_front();
	}
	ll front(ll x){
		clf(x);
		return S.front();
	}
	bool sp(ll x){
		ll back=S.size()-1;
		return uper(x,S[back-1],S[back]);
	}
	void clb(ll x){
		while(S.size()>1&&sp(x)) S.pop_back();
	}
	void push_back(ll x){
		clb(x);
		S.push_back(x);
	}
}Q;
void dp(void){
	ll i;
	for(i=1;i<=n;i++){
		Q.push_back(i);
		f[i]=fig(i,Q.front(i));
	}
	cout<<f[n]<<endl;
}
void init(void){
	cin>>n;
	ll i;
	for(i=0;i<n;i++) cin>>il[i].l>>il[i].w;
	sort(il,il+n);//此时按l有序
	ll nowmax=0;
	for(i=n-1;i>=0;i--){
		if(il[i].w>nowmax){
			nowmax=il[i].w;
			lis.push_front(il[i]);
		}
	}
	n=lis.size();
	ll temp=lis[0].w;
	lis.push_front((LAND){1,1});
}
int main(){
	freopen("acquire.in","r",stdin);
	freopen("acquire.out","w",stdout);
	init();
	dp();
	return 0;
}