結果
問題 |
No.472 平均順位
|
ユーザー |
![]() |
提出日時 | 2017-09-20 17:53:02 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,075 bytes |
コンパイル時間 | 490 ms |
コンパイル使用メモリ | 57,944 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 09:09:25 |
合計ジャッジ時間 | 2,371 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 14 WA * 2 |
ソースコード
#include<iostream> #include<algorithm> #include<cstdio> #define INF (1<<30) using namespace std; int n,p,a[5001],b[5001],c[5001]; double dp[2][15001],ans;//iコンテストまでにj解いた時の平均順位の最低値 int main(){ cin>>n>>p; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]>>c[i]; } for(int i=1;i<=n;i++){ for(int j=0;j<=3*i;j++){ if(j==0){ dp[1][j]=(dp[1-1][j]+a[1]); } else if(j==1){ dp[1][j]=min((dp[1-1][0]+b[i]),(dp[1-1][1]+a[i])); } else if(j==2){ dp[1][j]=min(min((dp[1-1][0]+c[i]),(dp[1-1][1]+b[i])),(dp[1-1][2]+a[i])); } else if(j==3*i){ dp[1][j]=(dp[1-1][j-3]+1); } else if(j==3*i-1){ dp[1][j]=min((dp[1-1][j-3]+1),(dp[1-1][j-2]+c[i])); } else if(j==3*i-2){ dp[1][j]=min(min((dp[1-1][j-3]+1),(dp[1-1][j-2]+c[i])),(dp[1-1][j-1]+b[i])); } else{ dp[1][j]=min(min(min(dp[1-1][j-3]+1,dp[1-1][j-2]+c[i]),dp[1-1][j-1]+b[i]),dp[1-1][j]+a[i]); } } for(int j=0;j<=3*i;j++){ dp[0][j]=dp[1][j]; dp[1][j]=0; } } ans=(double)dp[0][p]/n; printf("%.10f\n",ans); return 0; }