记录编号	184155	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Sue的小球	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.432 s
提交时间	2015-09-02 14:35:16	内存使用	15.83 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const double BASE=1000.0;
double DP1(int i,int j);
double DP2(int i,int j);
double f1[1010][1010]={0},f2[1010][1010]={0};
int w[1010][1010]={0},sum[1010]={0};
int N,X;
class miku
{
	public:
	int x,y,v;
}egg[1010];
double abs(double a)
{
	if(a<0) return -a;
	else return a;
}
double max(double a,double b)
{
	if(a>b) return a;
	else return b;
}
double DP1(int i,int j)
{
	if(f1[i][j]) return f1[i][j];
	f1[i][j]=max(DP1(i+1,j)-abs(egg[i+1].x-egg[i].x)*w[i+1][j],DP2(i+1,j)-abs(egg[j].x-egg[i].x)*w[i+1][j]);
	f1[i][j]+=double(egg[i].y);
	return f1[i][j];
}
double DP2(int i,int j)
{
	if(f2[i][j]) return f2[i][j];
	f2[i][j]=max(DP1(i,j-1)-abs(egg[i].x-egg[j].x)*w[i][j-1],DP2(i,j-1)-abs(egg[j-1].x-egg[j].x)*w[i][j-1]);
	f2[i][j]+=double(egg[j].y);
	return f2[i][j];
}
bool cmp(miku a,miku b)
{
	return a.x<b.x;
}
int main()
{
	freopen("sueball.in","r",stdin);
	freopen("sueball.out","w",stdout);
	scanf("%d%d",&N,&X);
	for(int i=1;i<=N;i++)
		scanf("%d",&egg[i].x);
	for(int i=1;i<=N;i++)
		scanf("%d",&egg[i].y);
	for(int i=1;i<=N;i++)scanf("%d",&egg[i].v);
	sort(egg+1,egg+1+N,cmp);
	for(int i=1;i<=N;i++) sum[i]=sum[i-1]+egg[i].v;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=i;j++)
			w[j][i]=sum[N]-sum[i]+sum[j-1];
	}
	for(int i=1;i<=N;i++)
	{
		f2[i][i]=f1[i][i]=(egg[i].y-abs(egg[i].x-X)*sum[N]);
		//cout<<i<<" "<<f1[i][i]<<" "<<f2[i][i]<<endl;
	}
	double ans=max(DP1(1,N),DP2(1,N));
	ans/=BASE;
	printf("%.3lf",ans);
	return 0;
}