比赛 |
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);
}