結果

問題 No.472 平均順位
ユーザー koba-e964
提出日時 2016-12-23 01:37:55
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
AC  
実行時間 156 ms / 2,000 ms
コード長 626 bytes
コンパイル時間 777 ms
コンパイル使用メモリ 59,128 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-17 14:18:38
合計ジャッジ時間 2,524 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <cstdio>
#include <iostream>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;

const int W = 150100;

int dp[2][W];
const int inf = 1e9;

int main(void){
  int n, p;
  cin >> n >> p;
  REP(j, 0, W) {
    dp[0][j] = dp[1][j] = inf;
  }
  dp[0][0] = 0;
  REP(i, 1, n + 1) {
    int t = i % 2;
    int a[4];
    REP(j, 0, 3) { cin >> a[j]; }
    a[3] = 1;
    REP(j, 0, 3 * i + 1) {
      int res = inf;
      REP(k, 0, 4) {
	if (j >= k) {
	  res = min(res, dp[1 - t][j - k] + a[k]);
	}
      }
      dp[t][j] = res;
    }
  }
  printf("%.15f\n", dp[n % 2][p] / 1.0 / n);
}
0