记录编号	185835	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-09-09 15:53:22	内存使用	0.37 MiB

#include<cstdio>
#include<iostream>
#include<deque>
using namespace std;
const int INF=0x7fffffff/2;
int N,S;
int F[5010],T[5010];
int D[5010];
deque<int> Q;
int t(int x,int y)
{
	return T[x]-T[y+1];
}
void DP()
{
	Q.push_back(N+1);
	D[N+1]=0;
	for(int i=N;i>=1;i--)
	{
		while(Q.size()>=2&&D[Q[1]]-D[Q[0]]<=F[i]*t(Q[1],Q[0]-1)) Q.pop_front();
		D[i]=D[Q[0]]+F[i]*(S+t(i,Q[0]-1));
		while(Q.size()>=2&&(D[i]-D[Q[Q.size()-1]])*t(Q[Q.size()-1],Q[Q.size()-2]-1)<=(D[Q[Q.size()-1]]-D[Q[Q.size()-2]])*t(i,Q[Q.size()-1]-1)) Q.pop_back();
		Q.push_back(i);
	}
	//for(int i=1;i<=N;i++)
	//	cout<<D[i]<<endl;
	printf("%d\n",D[1]);
}
int main()
{
	freopen("batch.in","r",stdin);
	freopen("batch.out","w",stdout);
	scanf("%d%d",&N,&S);
	for(int i=1;i<=N;i++)
		scanf("%d%d",&T[i],&F[i]);
	for(int i=N;i>=1;i--)
	{
		D[i]=INF;
		F[i]=F[i]+F[i+1];
		T[i]=T[i]+T[i+1];
	}
	DP();
	//cout<<D[1]<<endl;
	return 0;
}