結果

問題 No.472 平均順位
コンテスト
ユーザー murabito1129
提出日時 2025-04-18 14:14:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,022 bytes
コンパイル時間 2,297 ms
コンパイル使用メモリ 195,764 KB
実行使用メモリ 296,832 KB
最終ジャッジ日時 2025-04-18 14:14:48
合計ジャッジ時間 5,767 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;
//template<typename T> bool chmin(T& a,T b){if(a>b){a = b; return true;} return false;}
//template<typename T> bool chmax(T& a,T b){if(a<b){a = b; return true;} return false;}

int main(){
  int n,p; cin >> n >> p;
  vector<int> a(n),b(n),c(n);
  for(int i=0; n>i; ++i) cin >> a[i] >> b[i] >> c[i];
  //cost/val =  0/a[i],1/b[i],2/c[i],3/1
  //dp[n][p] := n問まで見てcostpとなった時の順位の総和の最小値
  int dp[n+1][p+1];
  for(int i=0; n>=i; ++i){
    for(int j=0; p>=j; ++j){
      dp[i][j] = inf;
    }
  }
  dp[0][0] = 0;
  for(int i=0; n>i; ++i){
    for(int j=0; p>=j; ++j){
      dp[i+1][j+0] = min(dp[i+1][j+0],dp[i][j]+a[i]);
      if(j+1<=p) dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j]+b[i]);
      if(j+2<=p) dp[i+1][j+2] = min(dp[i+1][j+2],dp[i][j]+c[i]);
      if(j+3<=p) dp[i+1][j+3] = min(dp[i+1][j+2],dp[i][j]+1);
    }
  }
  double ans = double(dp[n][p])/double(n);
  cout << setprecision(15) << fixed << ans << endl;
}
0