Submission #15318

#	Time	Username	Problem	Language	Result	Execution time	Memory
15318		gs14004	최적의 능력 구성 (kriii3_C)	C++14	62 / 62	171 ms	10300 KiB

C

#include <cstdio>
#include <algorithm>
using namespace std;

double dp[1<<20];
bool vis[1<<20];

int n;
int p[21], d[21];

double f(int x){
	if(x == 0) return 0;
	if(vis[x]) return dp[x];
	double ret = 0;
	int cnt = 0;
	for(int i=0; i<n; i++){
		if((x >> i) & 1){
			cnt++;
			ret += 0.01 * p[i] * d[i] + (1 - 0.01 * p[i]) * f(x ^ (1<<i));
		}
	}
	ret /= cnt;
	vis[x] = 1;
	return dp[x] = ret;
}
int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&p[i],&d[i]);
	}
	double ret = 0;
	for(int i=0; i<(1<<n); i++){
		ret = max(ret,f(i));
	}
	printf("%.8f",ret);
}

• Subtask 1: 25 / 25
• Subtask 2: 37 / 37