记录编号	265339	评测结果	AAAAAAAAAAAAA
题目名称	[CEOI2004]锯木厂选址	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.047 s
提交时间	2016-06-02 15:29:22	内存使用	1.00 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=20010;
long long W[maxn],F[maxn],D[maxn],X[maxn];	
long long ans=2147483647;
int q[maxn],st,ed;
int main(){
#ifndef ONLINE_JUDGE
	freopen("two.in","r",stdin);
	freopen("two.out","w",stdout);
#endif
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&W[i],&D[i+1]);
		W[i]+=W[i-1];D[i+1]+=D[i];
		X[i]=X[i-1]+(D[i]-D[i-1])*W[i-1];
	}
	n+=1;
	X[n]=X[n-1]+(D[n]-D[n-1])*W[n-1];
	q[st]=1;
	for(int i=2;i<n;i++){
		while(st<ed){
			if(W[q[st+1]]*D[q[st+1]]-W[q[st]]*D[q[st]]<=
				D[i]*(W[q[st+1]]-W[q[st]]))
				st++;
			else break;	
		}
		ans=min(ans,X[n]+W[q[st]]*(D[q[st]]-D[i])+W[i]*(D[i]-D[n]));
		while(st<ed){
			if((W[i]*D[i]-W[q[ed]]*D[q[ed]])*(W[q[ed]]-W[q[ed-1]])<=
				(W[q[ed]]*D[q[ed]]-W[q[ed-1]]*D[q[ed-1]])*(W[i]-W[q[ed]]))
				ed--;
			else break;	
		}
		q[++ed]=i;
	}
	printf("%lld\n",ans);
	return 0;	
}