結果

問題 No.472 平均順位
ユーザー onakaT_TitaionakaT_Titai
提出日時 2018-10-14 14:36:56
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,462 bytes
コンパイル時間 1,085 ms
コンパイル使用メモリ 146,272 KB
実行使用メモリ 88,224 KB
最終ジャッジ日時 2024-05-07 17:52:35
合計ジャッジ時間 9,008 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,752 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 10 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 21 ms
5,376 KB
testcase_08 AC 192 ms
9,344 KB
testcase_09 AC 1,657 ms
45,312 KB
testcase_10 TLE -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

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