比赛 2022级DP专题练习赛5 评测结果 AAAAAAAAAA
题目名称 Sue的小球 最终得分 100
用户昵称 op_组撒头屯 运行时间 0.101 s
代码语言 C++ 内存使用 9.24 MiB
提交时间 2023-02-22 19:53:28
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1000+5;
int n,x0,x[N],y[N],v[N],sa[N],sb[N];
long long f[N][N][2];bool vis[N][N][2];pair<int,int>p[N];
long long dp(int l,int r,bool opt){
    if (l==r)return 1ll*abs(x[l])*sa[n];
    if (vis[l][r][opt])return f[l][r][opt];vis[l][r][opt]=1;
    return f[l][r][opt]=opt?min(dp(l,r-1,0)+1ll*(x[r]-x[l])*(sa[l-1]+sb[r]),dp(l,r-1,1)+1ll*(x[r]-x[r-1])*(sa[l-1]+sb[r])):min(dp(l+1,r,0)+1ll*(x[l+1]-x[l])*(sa[l]+sb[r+1]),dp(l+1,r,1)+1ll*(x[r]-x[l])*(sa[l]+sb[r+1]));
}
int main(){
	freopen ("sueball.in","r",stdin);freopen ("sueball.out","w",stdout);scanf("%d%d",&n,&x0);
	for (int i=1;i<=n;i++)scanf("%d",&p[i].first),p[i].first-=x0;
	for (int i=1;i<=n;i++)scanf("%d",&y[i]),y[i]+=y[i-1];
	for (int i=1;i<=n;i++)scanf("%d",&p[i].second);sort(p+1,p+n+1);
	for (int i=1;i<=n;i++)sa[i]=sa[i-1]+p[i].second,x[i]=p[i].first;
	for (int i=n;i>=1;i--)sb[i]=sb[i+1]+p[i].second;
	printf("%.3lf\n",1.0*(y[n]-min(dp(1,n,0),dp(1,n,1)))/1000);
}