Run ID 作者 问题 语言 测评结果 时间 内存 代码长度 提交时间
49414 pqwa20 神父过河 C++ 运行超时 1000 MS 244 KB 1442 2024-07-10 17:49:23

Tests(0/19):


#include<bits/stdc++.h> #define N 110 #define int long long using namespace std; int n,L,a[N],c[N]; int suma,sumc; int d1[2][N][5*N]; int dp[2][N][5*N]; double ans; template<typename T>void read(T &x) { x=0;char c=getchar();T neg=0; while(!isdigit(c))neg|=!(c^'-'),c=getchar(); while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); if(neg)x=(~x)+1; }//快读 template<typename T>void wr(T x) { if(x<0)putchar('-'),x=-x; if(x>9)wr(x/10); putchar((x-x/10*10)^48); return ; }//快写 signed main() { // freopen("krumpirkokrumpirko2.in","r",stdin); read(n);read(L); for(int i=1;i<=n;i++) read(a[i]),suma+=a[i]; for(int i=1;i<=n;i++) read(c[i]),sumc+=c[i]; memset(d1,127,sizeof d1); ans=d1[0][0][0]; memset(dp,-127,sizeof dp); dp[0][0][0]=d1[0][0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=min(i,L);j++) { for(int k=0;k<=suma;k++) { d1[i&1][j][k]=d1[(i-1)&1][j][k]; dp[i&1][j][k]=dp[(i-1)&1][j][k]; if(k>=a[i]&&j) { d1[i&1][j][k]=min(d1[i&1][j][k],d1[(i-1)&1][j-1][k-a[i]]+c[i]); dp[i&1][j][k]=max(dp[i&1][j][k],dp[(i-1)&1][j-1][k-a[i]]+c[i]); } } } } for(int i=0;i<=suma;i++) { if(d1[n&1][L][i]<1e10) { ans=min(ans,d1[n&1][L][i] * (sumc-d1[n&1][L][i]) *1.0/(i*(suma-i))); } if(dp[n&1][L][i]>-1e10) ans=min(ans,dp[n&1][L][i]*(sumc-dp[n&1][L][i])*1.0/(i*(suma-i))); } printf("%.3lf\n",ans); return 0; }


测评信息: