結果

問題 No.472 平均順位
ユーザー onakaT_TitaionakaT_Titai
提出日時 2018-10-14 14:36:56
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,462 bytes
コンパイル時間 1,119 ms
コンパイル使用メモリ 143,584 KB
実行使用メモリ 121,216 KB
最終ジャッジ日時 2024-11-30 12:44:32
合計ジャッジ時間 27,302 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}


map<pair<int, int>, Int> m;
int p[5001][4];
Int INF = 10000000000;

Int rec(int x, int y){
    if (x == 0){
        return m[{x, y}] = p[x][y]; 
    }
    if (m.find({x, y}) == m.end()) m[{x, y}] = INF;
    if (m[{x, y}] == INF){
        for (int i = 0; i < 4; i++){
            if (y-i > 3*x) continue;
            if (y-i < 0) continue;
            m[{x, y}] = min(m[{x, y}], rec(x-1, y-i) + p[x][i]);
        }
    }
    return m[{x, y}];
}


int main(){
    cin.tie(0);

    int N, P; cin >> N >> P;
    for (int i = 0; i < N; i++){
        cin >> p[i][0] >> p[i][1] >> p[i][2];
        p[i][3] = 1;
    }
    printf("%.12f", rec(N-1, P)/(double)N);
}
0