Submission #2456774


Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;

int a[50];
double dp[50][50],C[50][50];

int main(){
	C[0][0]=1;
	for(int i=1;i<50;i++)for(int j=0;j<=i;j++){
		if(j==0||j==i)C[i][j]=1;
		else C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
	int n,p,q;scanf("%d%d/%d",&n,&p,&q);
	vector<P>v;
	rep(i,n){
		rep(j,n){
			int b;scanf("%d",&b);
			a[i]+=b;
		}
		v.push_back(P(a[i],i));
	}
	sort(v.begin(),v.end(),[](P a,P b){
		if(a.first!=b.first)return a.first>b.first;
		return a.second<b.second;
	});
	double d=p/(double)q;
	dp[0][0]=1;
	rep(i,n)rep(j,n){
		if(dp[i][j]==0)continue;
		int s=v[i].second;
		rep(k,a[s]+1)rep(t,n-a[s]){
			if(i){
				if((k+t>j)||(k+t==j&&v[i-1].second>v[i].second))continue;
			}
			dp[i+1][k+t]+=dp[i][j]*C[a[s]][k]*pow(d,k)*pow(1-d,a[s]-k)
								*C[n-1-a[s]][t]*pow(1-d,t)*pow(d,n-1-a[s]-t);
		}
	}
	double ans=0;
	rep(i,n)ans+=dp[n][i];
	printf("%.12lf\n",ans);
}

Submission Info

Submission Time
Task C - 天下一プログラマーコンテスト1999
User autumn_eel
Language C++14 (GCC 5.4.1)
Score 600
Code Size 989 Byte
Status AC
Exec Time 20 ms
Memory 512 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:15:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int n,p,q;scanf("%d%d/%d",&n,&p,&q);
                                     ^
./Main.cpp:19:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    int b;scanf("%d",&b);
                        ^

Judge Result

Set Name All
Score / Max Score 600 / 600
Status
AC × 43
Set Name Test Cases
All 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 02_manual_01, 02_manual_02, 02_manual_03, 02_manual_04, 02_manual_05, 02_manual_06, 02_manual_07, 02_manual_08, 02_manual_09, 02_manual_10, 02_manual_11, 02_manual_12, 20_random_00, 20_random_01, 20_random_02, 20_random_03, 20_random_04, 20_random_05, 20_random_06, 20_random_07, 20_random_08, 20_random_09, 20_random_10, 20_random_11, 20_random_12, 20_random_13, 20_random_14, 20_random_15, 20_random_16, 20_random_17, 20_random_18, 20_random_19, 30_manual_13, 30_manual_14, 30_manual_15, 30_manual_16, 30_manual_17, 30_manual_18, 30_manual_19
Case Name Status Exec Time Memory
00_sample_01 AC 1 ms 256 KB
00_sample_02 AC 1 ms 256 KB
00_sample_03 AC 1 ms 256 KB
00_sample_04 AC 1 ms 256 KB
02_manual_01 AC 1 ms 256 KB
02_manual_02 AC 1 ms 256 KB
02_manual_03 AC 1 ms 256 KB
02_manual_04 AC 1 ms 256 KB
02_manual_05 AC 1 ms 256 KB
02_manual_06 AC 1 ms 256 KB
02_manual_07 AC 1 ms 256 KB
02_manual_08 AC 2 ms 512 KB
02_manual_09 AC 1 ms 256 KB
02_manual_10 AC 1 ms 256 KB
02_manual_11 AC 1 ms 256 KB
02_manual_12 AC 1 ms 256 KB
20_random_00 AC 4 ms 256 KB
20_random_01 AC 4 ms 256 KB
20_random_02 AC 2 ms 256 KB
20_random_03 AC 2 ms 256 KB
20_random_04 AC 4 ms 256 KB
20_random_05 AC 3 ms 256 KB
20_random_06 AC 3 ms 256 KB
20_random_07 AC 2 ms 256 KB
20_random_08 AC 3 ms 256 KB
20_random_09 AC 3 ms 256 KB
20_random_10 AC 5 ms 256 KB
20_random_11 AC 3 ms 256 KB
20_random_12 AC 2 ms 256 KB
20_random_13 AC 1 ms 256 KB
20_random_14 AC 1 ms 256 KB
20_random_15 AC 2 ms 256 KB
20_random_16 AC 3 ms 256 KB
20_random_17 AC 3 ms 256 KB
20_random_18 AC 2 ms 256 KB
20_random_19 AC 3 ms 256 KB
30_manual_13 AC 18 ms 256 KB
30_manual_14 AC 6 ms 256 KB
30_manual_15 AC 5 ms 256 KB
30_manual_16 AC 19 ms 256 KB
30_manual_17 AC 2 ms 256 KB
30_manual_18 AC 20 ms 256 KB
30_manual_19 AC 20 ms 256 KB