记录编号	80985	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	Launcher	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2013-11-08 08:31:32	内存使用	3.26 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int a[5002]={0},t[5002]={0};
int T[5002]={0};
int f[5002]={0};
int sf[5002]={0};
int st[5002]={0};
int main()
{
	freopen("batch.in","r",stdin);
	freopen("batch.out","w",stdout);
	int i,j,k,l,s,p;
	cin>>n;
	cin>>s;
	for (i=1;i<=n;i++)
	{
		cin>>T[i]>>a[i];
		sf[i]=sf[i-1]+a[i];
		st[i]=st[i-1]+T[i];
	}
	f[1]=(s+T[1])*a[1];
	t[1]=s+T[1];
	for (i=2;i<=n;i++)
	{
		f[i]=f[i-1]+(t[i-1]+T[i]+s)*a[i];
		t[i]=t[i-1]+T[i]+s;
 
		for (j=i-2;j>=0;j--)
		{
			p=sf[n]-sf[j];
			if (f[i]+(sf[n]-sf[i])*t[i]>=f[j]+p*(t[j]+st[i]-st[j]+s))
			{
				f[i]=f[j]+(sf[i]-sf[j])*(t[j]+st[i]-st[j]+s);
				t[i]=t[j]+(st[i]-st[j])+s;
			}
		}
	}
	//for (i=1;i<=n;i++)
	//	 cout<<f[i]<<' '<<t[i]<<endl;
	cout<<f[n]<<endl;
	return 0;
}