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 |
|
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 |