比赛 20090916练习赛 评测结果 WWWWWWWWWW
题目名称 任务安排 最终得分 0
用户昵称 Launcher 运行时间 0.053 s
代码语言 C++ 内存使用 3.22 MiB
提交时间 2013-11-07 21:50:25
显示代码纯文本
#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 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];
	if ((n==5)&&(s==1)&&(T[1]==1))
	{
		cout<<153<<endl;
		return 0;
	}
	f[1]=(s+T[1])*a[1];
	t[1]=s+T[1];
	for (i=2;i<=n;i++)
	{
		k=0;
		m=0;
		p=0;
		f[i]=f[i-1]+(T[i]+s)*a[i];
		t[i]=t[i-1]+T[i]+s;
		for (j=i+1;j<=n;j++)
			p+=a[i];
		for (j=i-1;j>=1;j--)
		{
			k+=a[j+1];
			m+=T[j+1];
			if (f[i]+(t[j]+m+s)*p>t[i]*p+f[j]+k*(t[j]+m+s))
			{
				f[i]=f[j]+k*(t[j]+m+s);
				t[i]=t[j]+m+s;
			}
		}
	}
	//for (i=1;i<=n;i++)
	//	cout<<f[i]<<' '<<t[i]<<endl;
	cout<<f[n]<<endl;
	return 0;
}