Submission #3972166


Source Code Expand

#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<chrono>
#include<stack>
#include<fstream>
#include<list>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,x) unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;

struct rnk {
	ll win; ll name;
};

ll const MAX = 300;
bool grid[MAX][MAX];
ll w[MAX] = {};
rnk r[MAX];

bool ord(rnk x, rnk y) {
	return x.win > y.win;
}

long double dp[MAX][MAX] = {};
ll n;
long double p, q;

ll cmb[MAX][MAX];
long double ppow[MAX], qpow[MAX];

void init() {
	REP(i, 0, 100) {
		cmb[i][0] = cmb[i][i] = 1;
	}
	REP(i, 1, 100) {
		REP(j, 1, i - 1) {
			cmb[i][j] = cmb[i - 1][j - 1] + cmb[i - 1][j];
			//cout << i << " " << j << " cmb " << cmb[i][j] << endl;
		}
	}
	ppow[0] = qpow[0] = 1;

	REP(i, 1, n * 2) {
		ppow[i] = ppow[i - 1] * p;
		qpow[i] = qpow[i - 1] * q;
	}
}

int main() {
	cout.precision(13);
	string s;
	cin >> n >> s;
	ll ppp, qqq;
	if (s[1] == '/') {
		ppp = s[0] - '0';
		qqq = stoi(s.substr(2, SIZE(s)));
	}
	else {
		ppp = 10;
		qqq = 10;
	}
	long double pp = ppp;
	long double qq = qqq;
	p = pp / qq;
	q = 1.0 - p;
	init();
	REP(i, 1, n) {
		REP(j, 1, n) {
			cin >> grid[i][j];
		}
	}
	REP(i, 1, n) {
		ll cnt = 0;
		REP(j, 1, n) {
			cnt += (grid[i][j] == 1);
		}
		r[i] = { cnt,i };
	}
	SORT_O(r, n, ord);
	r[0] = { n,-1 };
	dp[0][n - 1] = 1;
	REP(i, 1, n) {
		ll w = r[i].win;
		ll l = n - 1 - w;
		REP(j, 0, w) {
			REP(k, 0, l) {
				long double cp = ppow[n - 1 - j - k] * qpow[j + k] * cmb[w][j] * cmb[l][k];

				ll cw = w - j + k;
				ll bw = cw + (r[i - 1].name > r[i].name);
				long double bp = 0;
				PER(bi, n-1 , bw) {
					bp += dp[i - 1][bi];
				}
				dp[i][cw] += bp * cp;
			}
		}
	}
	long double ans = 0;
	PER(i, n - 1, 0) {
		ans += dp[n][i];
	}
	cout << ans << endl;
	/*
	REP(i, 0, n) {
		REP(j, 0, n - 1) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/
}

Submission Info

Submission Time
Task C - 天下一プログラマーコンテスト1999
User nejineji
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2435 Byte
Status WA
Exec Time 2 ms
Memory 640 KB

Judge Result

Set Name All
Score / Max Score 0 / 600
Status
AC × 40
WA × 3
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 512 KB
00_sample_02 AC 1 ms 512 KB
00_sample_03 AC 2 ms 512 KB
00_sample_04 AC 1 ms 512 KB
02_manual_01 AC 2 ms 512 KB
02_manual_02 AC 1 ms 512 KB
02_manual_03 AC 2 ms 512 KB
02_manual_04 AC 2 ms 512 KB
02_manual_05 AC 2 ms 512 KB
02_manual_06 AC 2 ms 512 KB
02_manual_07 AC 2 ms 512 KB
02_manual_08 AC 2 ms 512 KB
02_manual_09 AC 2 ms 512 KB
02_manual_10 AC 1 ms 512 KB
02_manual_11 AC 1 ms 512 KB
02_manual_12 AC 2 ms 512 KB
20_random_00 AC 2 ms 640 KB
20_random_01 AC 2 ms 640 KB
20_random_02 AC 2 ms 512 KB
20_random_03 AC 2 ms 512 KB
20_random_04 AC 2 ms 640 KB
20_random_05 AC 2 ms 512 KB
20_random_06 WA 2 ms 512 KB
20_random_07 AC 2 ms 512 KB
20_random_08 AC 2 ms 512 KB
20_random_09 AC 2 ms 640 KB
20_random_10 AC 2 ms 640 KB
20_random_11 AC 2 ms 512 KB
20_random_12 AC 2 ms 512 KB
20_random_13 AC 2 ms 512 KB
20_random_14 AC 2 ms 512 KB
20_random_15 AC 2 ms 512 KB
20_random_16 AC 2 ms 512 KB
20_random_17 AC 2 ms 512 KB
20_random_18 AC 2 ms 512 KB
20_random_19 AC 2 ms 512 KB
30_manual_13 AC 2 ms 640 KB
30_manual_14 AC 2 ms 640 KB
30_manual_15 WA 2 ms 640 KB
30_manual_16 AC 2 ms 640 KB
30_manual_17 WA 2 ms 640 KB
30_manual_18 AC 2 ms 640 KB
30_manual_19 AC 2 ms 640 KB