技術室奥プログラミングコンテスト#4 Day2 G問題 - 平均レーティング

Source

技術室奥プログラミングコンテスト#4 Day2
問題文

問題概要

省略

解法

省略

cLayversion 20190902-1)のコード

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: 2021年09月28日23時11分22秒
Last modified: 2019年09月04日00時12分46秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: