记录编号	177255	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-08-11 15:03:00	内存使用	0.58 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=10000+10;
int n,s,tt[maxn],f[maxn];
/**********/double sumt[maxn];/**********/
int dp[maxn],q[maxn],sumf[maxn];
int head,t;

void headdelete(int i){
	while (head<t&&(dp[q[head+1]]-dp[q[head]])/(sumt[q[head]-1]-sumt[q[head+1]-1])<=sumf[i]) head++; //不能写<=!!!!!!
}

void taildelete(int i){
	while (head<t&&(dp[i]-dp[q[t]])/(sumt[q[t]-1]-sumt[i-1])<=(dp[q[t]]-dp[q[t-1]])/(sumt[q[t-1]-1]-sumt[q[t]-1]))  t--;
	q[++t]=i;
}

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",&tt[i],&f[i]);
		sumt[i]=sumt[i-1]+tt[i];
	}
	for (int i=n;i>=1;--i) sumf[i]=sumf[i+1]+f[i];
	dp[n+1]=0; q[1]=n+1;
	head=1; t=1;
	for (int i=n;i>=1;--i){
		headdelete(i);
		dp[i]=dp[q[head]]+(s+sumt[q[head]-1]-sumt[i-1])*sumf[i];
		taildelete(i);
	}
	printf("%d",dp[1]);
	//system("pause");
	return 0;
}