记录编号	142710	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]设计铁路	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2014-12-10 15:05:29	内存使用	3.15 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=40010;
class Point{
public:
	LL x,y;
};
Point operator - (Point a,Point b){return (Point){a.x-b.x,a.y-b.y};}
LL cross(Point a,Point b){//a逆时针到b的有向三角形面积
	return a.x*b.y-b.x*a.y;
}
class Hull{//下凸壳
public:
	Point s[SIZEN];
	int n,head,tail;//0~n-1
	void clear(void){n=0;head=tail=0;}
	Hull(void){clear();}
	void insert(Point p){
		while(n>=2&&cross(s[tail-1]-p,s[tail-2]-p)>=0) n--,tail--;
		s[tail++]=p;n++;
	}
	LL calc(Point a,LL k){
		return a.x*k+a.y;
	}
	LL calc(LL k){
		while(n>=2&&calc(s[head],k)>=calc(s[head+1],k)) n--,head++;
		return calc(s[head],k);
	}
}H;
LL N,M;
pair<LL,LL> V[SIZEN];//村庄们
LL RS[SIZEN]={0},MS[SIZEN]={0};//RS是R的前缀和,MS是R*T的前缀和
LL f[SIZEN]={0};
Point turn_point(int k){
	return (Point){V[k].first,f[k]-MS[k]+V[k].first*RS[k]};
}
void work(void){
	H.clear();
	H.insert(turn_point(0));
	for(int i=1;i<=N;i++){
		f[i]=H.calc(-RS[i-1])+M+MS[i-1];
		H.insert(turn_point(i));
	}
	printf("%lld\n",H.calc(-RS[N])+MS[N]);//即f[N+1]-M
}
void init(void){
	scanf("%lld%lld",&N,&M);
	for(int i=1;i<=N;i++) scanf("%lld%lld",&V[i].first,&V[i].second);
	sort(V+1,V+1+N);
	for(int i=1;i<=N;i++){
		RS[i]=RS[i-1]+V[i].second;
		MS[i]=MS[i-1]+(V[i].first*V[i].second);
	}
}
int main(){
	freopen("nt2011_design.in","r",stdin);
	freopen("nt2011_design.out","w",stdout);
	init();
	work();
	return 0;
}