Submission #65033916

---

Source Code Expand

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

//#define filename "xxx" 
#define FileOperations() freopen(filename".in", "r", stdin), freopen(filename".out", "w", stdout)
//#define multi_cases 1

#define inf 0x3f3f3f3f
#define Linf 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int> 
#define all(v) v.begin(), v.end()
#define upw(i, a, b) for(int i = (a); i <= (b); ++i)
#define dnw(i, a, b) for(int i = (a); i >= (b); --i)

template<class T> bool vmax(T &a, T b) { return b > a ? a = b, true : false; }
template<class T> bool vmin(T &a, T b) { return b < a ? a = b, true : false; }
template<class T> void clear(T &x) { T().swap(x); }

const int N = 10;

int n, x, s[N], c[N];
double p[N];

double f[5002][1000];
double calc(int x, int S) {
	if(f[x][S] > 1e-6) return f[x][S];
	upw(i, 1, n) if(c[i] <= x && !(S >> i & 1)) 
		vmax(f[x][S], p[i] * (s[i] + calc(x - c[i], S | 1 << i)) + (1 - p[i]) * calc(x - c[i], S));
	return f[x][S];
}

void Traveller() {
	cin >> n >> x;
	upw(i, 1, n) cin >> s[i] >> c[i] >> p[i], p[i] /= 100;
	printf("%.6f\n", calc(x, 0));
}

signed main() {
#ifdef filename
	FileOperations();
#endif
	
	signed _ = 1;
#ifdef multi_cases
	scanf("%d", &_);
#endif
	while(_--) Traveller();
	return 0;
}

Submission Info

Judge Result