結果

問題 No.472 平均順位
コンテスト
ユーザー kimiyuki
提出日時 2016-12-22 13:13:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 943 ms / 2,000 ms
コード長 795 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 53,076 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-17 14:18:14
合計ジャッジ時間 4,550 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <vector>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
typedef long long ll;
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
const int inf = 1e9+7;
int main() {
    int n, p; scanf("%d%d", &n, &p);
    vector<array<int, 4> > th(n);
    repeat (i,n) {
        repeat (j,3) scanf("%d", &th[i][j]);
        th[i][3] = 1;
    }
    vector<int> cur(p+1, inf);
    vector<int> prv;
    cur[0] = 0;
    repeat (i,n) {
        cur.swap(prv);
        cur.clear();
        cur.resize(p+1, inf);
        repeat (k,p+1) {
            repeat (j,4) if (k+j < p+1) {
                setmin(cur[k+j], prv[k] + th[i][j]);
            }
        }
    }
    printf("%.8lf\n", cur[p] /(double) n);
    return 0;
}
0