记录编号	249199	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-04-12 12:31:00	内存使用	0.41 MiB

#include<cstdio>
#include<cstdlib>
#define N 5010

int n,s,t[N],f[N];
int st[N],sf[N],dp[N],C;
int Q[N],head,tail;
inline int cost(int j,int i){return dp[j]+s*(sf[n]-sf[j])+(sf[i]-sf[j])*st[i];}
inline bool cmp(int a,int b,int c)
{
	return (dp[a]-dp[b]-s*(sf[a]-sf[b]))*(sf[b]-sf[c])>=(dp[b]-dp[c]-s*(sf[b]-sf[c]))*(sf[a]-sf[b]);
}

int main()
{
	//freopen("a.txt","r",stdin);
	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]);
		st[i]=st[i-1]+t[i];
		sf[i]=sf[i-1]+f[i];
	}
	Q[tail++]=0;
	for(int i=1;i<=n;i++){
		while(tail-head>=2&&cost(Q[head],i)>cost(Q[head+1],i))
			head++;
		dp[i]=cost(Q[head],i);
		while(tail-head>=2&&cmp(Q[tail-2],Q[tail-1],i)) 
			tail--;
		Q[tail++]=i;
		
		/*for(int j=0;j<i;j++)
			printf("%d ",cost(j,i));
		putchar('\n');
		for(int j=head;j<tail;j++)
			printf("%d %d ",Q[j],cost(Q[j],i));
		putchar('\n');*/
	}
	/*for(int i=1;i<=n;i++)
		printf("%d ",dp[i]);*/
	printf("%d",dp[n]);
	return 0;
}