QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#171351 | #2913. Archery Accuracy | yinshaziyue | RE | 0ms | 0kb | C++17 | 1.8kb | 2023-09-09 16:50:59 | 2023-09-09 16:51:00 |
answer
#include<bits/stdc++.h>
using namespace std;
int n, s[18];
double p[18], dp[80000];
struct matrix {
double a[2][2];
matrix operator*(const matrix& rhs) const {
matrix ret;
for (int i = 0; i <= 1; ++i) {
for (int j = 0; j <= 1; ++j) {
ret.a[i][j] = 0;
for (int k = 0; i <= 1; ++k) {
ret.a[i][j] += a[i][k] * rhs.a[k][j];
}
}
}
return ret;
}
matrix operator^(const int& k) const {
matrix m = *this,ret;
for (int i = 0; i <= 1; ++i) {
for (int j = 0; j <= 1; ++j) {
ret.a[i][j] = (i == j);
}
}
int y = k;
while (y) {
if (y & 1) ret = ret * m;
m = m * m;
y >>= 1;
}
return ret;
}
};
double f(int a, int b, double p) {
matrix m,mn,ma;
m.a[0][0] = 0, m.a[0][1] = 1;
m.a[1][0] = 1 - 1 / p, m.a[1][1] = 1 / p;
mn = m ^ (a + b);
double x = 1 / mn.a[0][1];
ma = m ^ a;
double ret = ma.a[0][1] * x;
return ret;
}
int main() {
cin >> n;
for (int i = 0; i <= n - 1; ++i) {
cin >> p[i];
}
s[0] = 0;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
dp[0] = 1;
for (int S = 1; S <= (1 << n) - 1; ++S) {
int t = __builtin_popcount(S);
dp[S] = 0;
for (int i = 0; i <= n - 1; ++i) {
if (S & (1 << i)) {
int S0 = S - (1 << i);
dp[S] = max(dp[S], dp[S0] * f(s[t] + s[t - 1], s[t] - s[t - 1], p[i]) + (1 - dp[S0]) * f(s[t] - s[t - 1], s[t] + s[t - 1], p[i]));
}
}
}
cout << fixed << setprecision(8) << dp[(1 << n) - 1] << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
17 0.49 0.45 0.50 0.47 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.49 0.50 0.49 0.50 0.49 15 16 17 18 19 20 26 29 86 88 89 93 95 96 97 98 100