Submission #65002666

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define FastIO
#ifdef FastIO
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin)),*p2=0,*p1++)
#endif //#ifdef FastIO
using namespace std;int n,m,k;
namespace IO{char buf[8888888],*p1=buf,*p2=buf,ibuf;
int rd(int x=0,int f=1){for(;!isdigit(ibuf);ibuf=getchar())ibuf=='-'&&(f=-1);for(;isdigit(ibuf);ibuf=getchar())x=(x<<1)+(x<<3)+(ibuf^48);return x*f;}
int rds(char*s,int n=0){for(;!isgraph(ibuf);ibuf=getchar());for(;isgraph(ibuf);ibuf=getchar())s[n++]=ibuf;return s[n]=0,n;}
}using IO::rd;using IO::rds;//namespace IO
#define fio(s) (freopen(s".in","r",stdin),freopen(s".out","w",stdout))

int s[5050],c[5050];
double p[5050];
double f[256][5050];

signed main(){int Tst=1;
//Tst=rd();
while(Tst--){

	n=rd();
	m=rd();
	for(int i=0;i<n;i++)s[i]=rd(),c[i]=rd(),p[i]=rd()*0.01;
	for(int i=0;i<(1<<n);i++)
	{
		for(int j=0;j<=m;j++)
		{
			for(int k=0;k<n;k++)if(i>>k&1)
			{
				if(j>=c[k])f[i][j]=max(f[i][j],f[i][j-c[k]]*(1-p[k])+p[k]*(f[i^(1<<k)][j-c[k]]+s[k]));
			}
		}
	}
	printf("%.14lf\n",f[(1<<n)-1][m]);

//newline!
}return 0;}

Submission Info

Judge Result