QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#171351#2913. Archery AccuracyyinshaziyueRE 0ms0kbC++171.8kb2023-09-09 16:50:592023-09-09 16:51:00

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 16:51:00]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-09-09 16:50:59]
  • 提交

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

詳細信息

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

output:


result: