文件详细信息

下载本文件

本文件的大小为 1139 字节。

#include<algorithm>
#include<cstdio>
#include<cstring>
template<typename T>
void read(T&num){
	bool flag=true;
	int ch=getchar();
	num=0;
	while(ch<48||ch>57){
		if(ch=='-')flag=false;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	flag||(num=-num);
}
typedef long long ll;
typedef double real;
const int maxn=50005,inf=0x3f3f3f3f;
int n,m;
struct Land{
	int w,l;
}a[maxn];
bool operator<(const Land a,const Land b){
	return a.w!=b.w?a.w<b.w:a.l<b.l;
}
ll f[maxn];
int q[maxn],front=1,tail;
real slope(int x,int y){
	return real(f[x]-f[y])/(a[x+1].l-a[y+1].l);
}
int main(){
	read(n);
	for(int i=1;i<=n;i++)read(a[i].w),read(a[i].l);
	std::sort(a+1,a+n+1);
	int max_l=-inf;
	m=n;
	for(int i=n;i>=1;i--){
		if(a[i].l<=max_l)a[i].w=inf,n--;
		max_l=std::max(max_l,a[i].l);
	}
	std::sort(a+1,a+m+1);
	memset(f+1,63,sizeof(ll)*n);
	q[++tail]=0;
	for(int i=1;i<=n;i++){
		while(front<tail&&slope(q[front],q[front+1])>-a[i].w)front++;
		f[i]=f[q[front]]+(ll)a[i].w*a[q[front]+1].l;
		while(front<tail&&slope(q[tail-1],q[tail])<slope(q[tail],i))tail--;
		q[++tail]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}