Submission #65030801

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Original Python code:
// def li():
//     return list(map(int, input().split()))
// import sys
// sys.setrecursionlimit(10**6)
// import pypyjit
// pypyjit.set_param('max_unroll_recursion=-1')
//
// n,x=li()
// scp=[li() for _ in range(n)]
// dp={}
// rr=[0]*(1<<n)
// for i in range(1<<n):
//     tmp=0
//     for j in range(n):
//         if (i>>j)&1:
//             tmp+=scp[j][0]
//     rr[i]=tmp
// def solve(state,val):
//     if (state,val) in dp:return dp[(state,val)]
//     res=rr[state]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

// Original Python code:
// def li():
//     return list(map(int, input().split()))
// import sys
// sys.setrecursionlimit(10**6)
// import pypyjit
// pypyjit.set_param('max_unroll_recursion=-1')
//
// n,x=li()
// scp=[li() for _ in range(n)]
// dp={}
// rr=[0]*(1<<n)
// for i in range(1<<n):
//     tmp=0
//     for j in range(n):
//         if (i>>j)&1:
//             tmp+=scp[j][0]
//     rr[i]=tmp
// def solve(state,val):
//     if (state,val) in dp:return dp[(state,val)]
//     res=rr[state]
//     
//     for i in range(n):
//         if (state>>i)&1:
//             continue
//         if val-scp[i][1]<0:continue
//         nxt=state+(1<<i)
//         tmp=(scp[i][2]/100)*solve(nxt,val-scp[i][1])+(1-scp[i][2]/100)*solve(state,val-scp[i][1])
//         res=max(res,tmp)
//     dp[(state,val)]=res
//     return res
// print(solve(0,x))

#include <bits/stdc++.h>
using namespace std;

int n, x;
vector<array<int, 3>> scp;
vector<int> rr;
map<pair<int, int>, double> dp;

double solve(int state, int val) {
    pair<int, int> key = {state, val};
    if (dp.count(key)) return dp[key];
    double res = rr[state];

    for (int i = 0; i < n; ++i) {
        if ((state >> i) & 1) continue;
        if (val - scp[i][1] < 0) continue;
        int nxt = state | (1 << i);
        double tmp = (scp[i][2] / 100.0) * solve(nxt, val - scp[i][1])
                   + (1.0 - scp[i][2] / 100.0) * solve(state, val - scp[i][1]);
        res = max(res, tmp);
    }

    dp[key] = res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> x;
    scp.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> scp[i][0] >> scp[i][1] >> scp[i][2];
    }

    int size = 1 << n;
    rr.resize(size, 0);
    for (int i = 0; i < size; ++i) {
        int tmp = 0;
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                tmp += scp[j][0];
            }
        }
        rr[i] = tmp;
    }

    cout << fixed << setprecision(10) << solve(0, x) << "\n";
    return 0;
}

Submission Info

Judge Result