记录编号	27428	评测结果	WWWWWWWAWW
题目名称	[IOI 2002] 任务安排	最终得分	10
用户昵称	donny	是否通过	未通过
代码语言	C++	运行时间	0.023 s
提交时间	2011-09-22 14:35:29	内存使用	0.32 MiB

#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

int n,i,j,k,l;
int s,t[5010],v[5010];
int f[5010];

int main()
{
	ifstream fin("batch.in");
	ofstream fout("batch.out");
	
	fin>>n>>s;
	
	for (i=1;i<=n;i++)
	{
		fin>>t[i]>>v[i];
	}
	
	for (i=n-1;i>=1;i--)
	{
		v[i]=v[i]+v[i+1];
		t[i]=t[i]+t[i+1];
	}
	
	t[n+1]=0;
	v[n+1]=0;
	
	f[n]=t[n]*v[n];
	f[n+1]=0;
	
	for (i=n-1;i>=1;i--)
	{
		f[i]=v[i]*t[i];
		for (j=i+1;j<=n;j++)
			if ((f[j]+(t[i]-t[j]+s)*v[i])<f[i])
				f[i]=f[j]+(t[i]-t[j]+s)*v[i];
	}
	
	fout<<f[1];
	
	fin.close();
	fout.close();
	
	return 0;
}