Submission #15417

#	Time	Username	Problem	Language	Result	Execution time	Memory
15417		pichulia	최적의 능력 구성 (kriii3_C)	C++98	62 / 62	256 ms	202812 KiB

C

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
struct A{
	int p, d;
	double q;
}a[100];
double x[1<<20];
double y[21][1<<20];
bool r[21][1<<20];
long long int fcnt[22];
int p[22];
int pl;
double dfs(int i, int cnt)
{
	if(r[cnt][i]) return y[cnt][i];
	r[cnt][i] = 1;
	
	if(cnt==0) return y[cnt][i] = 1;
	int j, k;
	double res=0;
	double sum = 0;
	int count = 0;
	for(j=0;j<pl;j++)
	{
		if(i&(1<<p[j]))
		{
			double tmp = dfs(i-(1<<p[j]), cnt-1);
			tmp *= (1 - a[j].p / 100.0);
			sum += tmp;
			count++;
		}
	}
	res = sum / count;
	return y[cnt][i] = res;
}
int main()
{
	int i, j, k;
	scanf("%d",&n);
	x[0] = 1;
	for(i=0;i<n;i++)
	{
		a[i].p = 20; a[i].d = 100;
		scanf("%d %d",&a[i].p,&a[i].d);
		a[i].q = a[i].d * a[i].p / 100.0;
	}
	for(i=1;i<(1<<n)-1;i++)
	{
		double temp = 1;
		int cnt=0;
		pl = 0;
		x[i] = 0;
		for(j=0;j<n;j++)
			if(i&(1<<j))
			{
				p[pl++] = j;
				cnt++;
				x[i] += (1-a[j].p/100.0)*(x[i-(1<<j)]);
			}
		x[i] /= cnt;
		x[i] += 1;
//		for(j=0;j<=cnt;j++)
		{
//			x[i] += dfs(i,j);
//			printf("%lf ",y[j][i]);
		}
//		printf("%lf\n",x[i]);
//		printf("\n");
	}
	double res=0;
	for(i=1;i<(1<<n);i++)
	{
		double temp = 0;
		int cnt=0;
		for(j=0;j<n;j++)
			if(i&(1<<j))
				cnt++;
		for(j=0;j<n;j++)
			if(i&(1<<j))
			{
				temp += x[i - (1<<j)] * a[j].q;
			}
		temp /= cnt;
		if(res < temp)
			res = temp;
	//	printf("%d %lf\n",i,temp);
	}
	printf("%.10lf\n",res);
}

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