记录编号	156089	评测结果	AAAAAAAAAAAAA
题目名称	[CEOI2004]锯木厂选址	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2015-04-02 10:11:01	内存使用	0.77 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x7fffffff;
const double eps=1e-10;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=20010;
int n;
int c[MAXN],h[MAXN],w[MAXN],d[MAXN],dp[MAXN];
int q[MAXN],tail=1,front=1;
int _ans=INF;
///==============function declaration============
double g(int j,int k){return double(w[j-1]*h[j]-w[k-1]*h[k])/double(h[j]-h[k]);}
void Calc(int i,int j);
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("two.in","r",stdin);
   freopen("two.out","w",stdout);
	//#endif 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&w[n-i+1],&d[n-i+1]);
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]+d[i];
		c[i]=c[i-1]+w[i]*h[i];
		w[i]+=w[i-1];
	}
	q[1]=0;dp[1]=0;
	for(int i=1;i<=n;i++){
		while (front<tail&&g(q[front+1],q[front])<w[i-1])
			front++;
		dp[i]=q[front];
		while (front<tail&&g(q[tail-1],q[tail])>g(q[tail],i))
			tail--;
		q[++tail]=i;
	}
	for(int i=2;i<=n;i++)
		Calc(dp[i],i);
	printf("%d\n",_ans);
   return 0;
}
///================fuction code====================
void Calc(int i,int j){
	int res=0;
	res=c[i-1];
	res=res+c[j-1]-c[i]-(w[j-1]-w[i])*h[i];
	res=res+c[n]-c[j]-(w[n]-w[j])*h[j];
	_ans=min(_ans,res);
}