fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define Long long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. void get_shit_done() {
  10.     int n, x;
  11.     cin >> n >> x;
  12.  
  13.     vector<int> S(n), C(n), P(n);
  14.     for (int i = 0; i < n; ++i) {
  15.         cin >> S[i] >> C[i] >> P[i];
  16.     }
  17.  
  18.     auto get = [&](int c) {
  19.         return 1.0 * (1.0 * c) / (100.0);
  20.     };
  21.  
  22.     vector<int> ord(n);
  23.     for (int i = 0; i < n; ++i) {
  24.         ord[i] = i;
  25.     }
  26.  
  27.     double ans = 0;
  28.     do {
  29.         vector<int> s(n), c(n), p(n);
  30.         for (int i = 0; i < n; ++i) {
  31.             s[i] = S[ord[i]];
  32.             c[i] = C[ord[i]];
  33.             p[i] = P[ord[i]];
  34.         }
  35.         vector<double> dp[2];
  36.         for (int i = 0; i < 2; ++i) {
  37.             dp[i].assign(x + 1, 0);
  38.         }
  39.         for (int i = n - 1, at = 1 - (n & 1); i >= 0; --i, at = 1 - at) {
  40.             dp[at].assign(x + 1, 0);
  41.             for (int have = 0; have <= x; ++have) {
  42.                 double leave = dp[1 - at][have], take = 0;
  43.                 if (have >= c[i]) {
  44.                     take = get(p[i]) * (s[i] + dp[1 - at][ have - c[i] ]);
  45.                     take += ( 1.0 - get(p[i]) ) * dp[at][ have - c[i] ];
  46.                 }
  47.                 dp[at][have] = max(leave, take);
  48.             }
  49.         }
  50.         ans = max(ans, dp[0][x]);
  51.     } while ( next_permutation( ord.begin(), ord.end() ) );
  52.  
  53.     cout << ans;
  54. }
  55.  
  56. signed main() {
  57.     _3bkarm
  58.  
  59.     cout << fixed << setprecision(8);
  60.  
  61.     int ts = 1;
  62. //    cin >> ts;
  63.     while (ts--) {
  64.         get_shit_done();
  65.     }
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.00000000
https://ideone.com/fZiqIs
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!