记录编号	165178	评测结果	AAAAAAAAAAAAA
题目名称	[CEOI2004]锯木厂选址	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.271 s
提交时间	2015-06-10 17:17:52	内存使用	5.92 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>

#define N 40010
#define INF 0x3f3f3f3f3f3f3f3fLL
#define LL long long

using namespace std;

int n;
LL w[N],d[N];
LL Sw[N],Sd[N],S[N];

LL Rand(){
	return ((LL)(rand())<<12LL)+(LL)rand();
}

LL calc(int a,int b){
	if(a>b) swap(a,b);
	LL ans=S[a];
	ans+=S[b]-S[a]-(Sd[b]-Sd[a])*Sw[a];
	ans+=S[n+1]-S[b]-(Sd[n+1]-Sd[b])*Sw[b];
	return ans;
}

int main(){
	freopen("two.in","r",stdin);
	freopen("two.out","w",stdout);
	srand(7648);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&d[i]);
	for(int i=1;i<=n;i++){
		Sd[i+1]=d[i]+Sd[i];
		Sw[i]=w[i]+Sw[i-1];
		S[i+1]=S[i]+d[i]*Sw[i];
	}
	LL ansv=INF;
	int minx[2],maxx[2],xt=n/2,yt=n/2,R=n/2;
	for(int t=1;t<=100&&R;t++,R=(int)(R*3.0/4.0)){
		minx[0]=max(xt-R,1);
		maxx[0]=min(xt+R,n);
		minx[1]=max(yt-R,1);
		maxx[1]=min(yt+R,n);
		for(int i=1;i<=9000;i++){
			int x=Rand()%(2*R)+minx[0];
			int y=Rand()%(2*R)+minx[1];
			if(calc(x,y)<ansv){
				ansv=calc(x,y);
				xt=x; yt=y;
			}
		}
	}
	printf("%lld\n",ansv);
	return 0;
}