省略
省略
C++に変換後のコードはこちら
int N, K, AA, A[1500], B[1500], C[1500], D[1500];
double dp[1501], memo[1501];
{
int i, j, k, t, tot, rem;
ll ks;
double s, g;
double res = 0, tmp, hoge;
double mn, mx;
rd(N,K,AA,(A,B,C,D)(N));
sortA(N,A,B,C,D);
mn = AA;
rep(i,N) mn += A[i];
mn /= N+1;
mx = AA;
rep(i,N) mx >?= (double)A[i] + (double)B[i] * (K / C[i]);
res = bsearch_max[double,z,mn,mx,E=1e-4][
rep(i,K+1) dp[i] = -double_inf;
dp[0] = AA - z;
rep(i,N) dp[0] += A[i] - z;
rep(i,N){
rep(j,K+1) memo[j] = dp[j];
rep(j,C[i],K+1) dp[j] >?= dp[j-C[i]] + B[i];
for(j=K;j>=D[i];j--) dp[j] >?= memo[j-D[i]] - (A[i] - z);
}
tmp = -1;
rep(i,K+1) tmp >?= dp[i];
](tmp >= 0);
wt(res);
}
Current time: 2024年03月29日05時50分15秒
Last modified: 2019年09月04日00時12分46秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)