Submission #1687784

---

Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;

vector<vector<vector<long double>>>dp;
vector<pair<int, int>>c_win;



int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N;
	string s;
	cin >> s;
	long double p;
	long double a = 0;
	long double b = 0;
	bool flag = true;
	for (auto i : s) {
		if (i == '/') {
			flag = false;
		}
		else if (flag) {
			a *= 10;
			a += i - '0';
		}
		else {
			b *= 10;
			b += i - '0';
		}
	}
	p = a / b;
	vector<vector<int>>battle(N);
	c_win.resize(N);
	for (int i = 0; i < N; i++) {
		c_win[i].second = N - i;
		for (int j = 0; j < N; j++) {
			cin >> K;
			if (i != j) {
				battle[i].push_back(K);
			}
			if (K) {
				c_win[i].first++;
			}
		}
	}
	sort(c_win.begin(), c_win.end());
	reverse(c_win.begin(), c_win.end());
	dp.resize(N, vector<vector<long double>>(N + 1, vector<long double>(N + 1)));
	for (int i = 0; i < N; i++) {
		dp[i][0][0] = 1;
		for (int j = 1; j < N; j++) {
			for (int k = 0; k < j; k++) {
				if (battle[i][j - 1]) {
					dp[i][j][k] += dp[i][j - 1][k] * ((long double)1 - p);
					dp[i][j][k + 1] += dp[i][j - 1][k] * p;
				}
				else {
					dp[i][j][k + 1] += dp[i][j - 1][k] * ((long double)1 - p);
					dp[i][j][k] += dp[i][j - 1][k] * p;
				}
			}
		}
	}
	vector<vector<long double>>ret(N, vector<long double >(N));
	for (int i = 0; i < N; i++) {
		ret[N - 1][i] = dp[N - c_win[N - 1].second][N - 1][i];
	}
	for (int i = N - 2; i >= 0; i--) {
		if (N - c_win[i + 1].second > N - c_win[i].second) {
			long double sum = 0;
			for (int j = 0; j < N; j++) {
				sum += ret[i + 1][j];
				ret[i][j] = sum*dp[N - c_win[i].second][N - 1][j];
			}
		}
		else {
			long double sum = 0;
			for (int j = 0; j < N; j++) {
				ret[i][j] = sum*dp[N - c_win[i].second][N - 1][j];
				sum += ret[i + 1][j];
			}
		}
	}
	long double ans = 0;
	for (int i = 0; i < N; i++) {
		ans += ret[0][i];
	}
	cout << setprecision(20) << ans << endl;
	return 0;
}

Submission Info

Judge Result