oj.uz

Submission #15417

# Submission time Handle Problem Language Result Execution time Memory
15417 2015-07-12T07:24:02 Z pichulia 최적의 능력 구성 (kriii3_C) C++
62 / 62
 256 ms 202812 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 202812 KB Output is correct
2 Correct 0 ms 202812 KB Output is correct
3 Correct 0 ms 202812 KB Output is correct
4 Correct 0 ms 202812 KB Output is correct
5 Correct 0 ms 202812 KB Output is correct
6 Correct 0 ms 202812 KB Output is correct
7 Correct 0 ms 202812 KB Output is correct
8 Correct 0 ms 202812 KB Output is correct
9 Correct 0 ms 202812 KB Output is correct
10 Correct 0 ms 202812 KB Output is correct
11 Correct 0 ms 202812 KB Output is correct
12 Correct 0 ms 202812 KB Output is correct
13 Correct 0 ms 202812 KB Output is correct
14 Correct 0 ms 202812 KB Output is correct
15 Correct 0 ms 202812 KB Output is correct
16 Correct 0 ms 202812 KB Output is correct
17 Correct 0 ms 202812 KB Output is correct
18 Correct 0 ms 202812 KB Output is correct
19 Correct 0 ms 202812 KB Output is correct
20 Correct 0 ms 202812 KB Output is correct
21 Correct 0 ms 202812 KB Output is correct
22 Correct 0 ms 202812 KB Output is correct
23 Correct 0 ms 202812 KB Output is correct
24 Correct 0 ms 202812 KB Output is correct
25 Correct 0 ms 202812 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 202812 KB Output is correct
2 Correct 251 ms 202812 KB Output is correct
3 Correct 255 ms 202812 KB Output is correct
4 Correct 255 ms 202812 KB Output is correct
5 Correct 255 ms 202812 KB Output is correct
6 Correct 254 ms 202812 KB Output is correct
7 Correct 256 ms 202812 KB Output is correct
8 Correct 249 ms 202812 KB Output is correct
9 Correct 254 ms 202812 KB Output is correct
10 Correct 254 ms 202812 KB Output is correct
11 Correct 243 ms 202812 KB Output is correct
12 Correct 250 ms 202812 KB Output is correct
13 Correct 254 ms 202812 KB Output is correct
14 Correct 253 ms 202812 KB Output is correct
15 Correct 254 ms 202812 KB Output is correct
16 Correct 252 ms 202812 KB Output is correct
17 Correct 255 ms 202812 KB Output is correct
18 Correct 254 ms 202812 KB Output is correct
19 Correct 247 ms 202812 KB Output is correct
20 Correct 250 ms 202812 KB Output is correct