Submission #563797

#	Time	Username	Problem	Language	Result	Execution time	Memory
563797		KoD	Bowling (BOI15_bow)	C++17	100 / 100	200 ms	3532 KiB

bow

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < int(n); ++i)

using ll = long long;
using std::vector;

ll dp[10][331][11][11];

bool match(const char c, const char d) {
    return c == '?' or c == d;
}

ll solve(const int N, const std::string& S, const std::vector<int>& P) {
    rep(i, 10) rep(j, 331) rep(k, 11) rep(l, 11) dp[i][j][k][l] = 0;
    rep(k, 11) rep(l, 11) dp[0][0][k][l] = 1;

    rep(i, N - 1) rep(j, 331) rep(k, 11) rep(l, 11) {
        const ll val = dp[i][j][k][l];
        if (val == 0)
            continue;

        const auto C = S.begin() + (2 * i);

        if (k == 10) {
            if (match(C[0], 'x') and match(C[1], '-')) {
                rep(m, 11) {
                    const int nj = j + 10 + l + m;
                    if (P[i] == -1 or P[i] == nj) {
                        dp[i + 1][nj][l][m] += val;
                    }
                }
            }
        } else {
            if (k + l <= 10 and match(C[0], char('0' + k))) {
                rep(m, 11) {
                    int nj = j;
                    if (k + l == 10) {
                        if (!match(C[1], '/'))
                            continue;
                        nj += 10 + m;
                    } else {
                        if (!match(C[1], char('0' + l)))
                            continue;
                        nj += k + l;
                    }
                    if (P[i] == -1 or P[i] == nj) {
                        rep(n, 11) dp[i + 1][nj][m][n] += val;
                    }
                }
            }
        }
    }

    const auto C = S.begin() + (2 * N - 2);
    ll ret = 0;
    rep(j, 331) {
        const auto check = [&](const int add) { return P[N - 1] == -1 or P[N - 1] == j + add; };
        if (match(C[0], 'x')) {
            if (match(C[1], 'x')) {
                if (match(C[2], 'x')) {
                    if (check(10 + 10 + 10)) {
                        ret += dp[N - 1][j][10][10];
                    }
                }
                rep(m, 10) {
                    if (match(C[2], char('0' + m)) and check(10 + 10 + m)) {
                        ret += dp[N - 1][j][10][10];
                    }
                }
            }
            rep(l, 10) {
                rep(m, 11) {
                    if (l + m == 10 and match(C[1], char('0' + l)) and match(C[2], '/') and
                        check(10 + l + m)) {
                        ret += dp[N - 1][j][10][l];
                    }
                    if (l + m < 10 and match(C[1], char('0' + l)) and
                        match(C[2], char('0' + m)) and check(10 + l + m)) {
                        ret += dp[N - 1][j][10][l];
                    }
                }
            }
        }
        rep(k, 10) {
            rep(l, 11) {
                if (k + l == 10 and match(C[0], char('0' + k)) and match(C[1], '/')) {
                    if (match(C[2], 'x') and check(10 + 10)) {
                        ret += dp[N - 1][j][k][l];
                    }
                    rep(m, 10) {
                        if (match(C[2], char('0' + m)) and check(10 + m)) {
                            ret += dp[N - 1][j][k][l];
                        }
                    }
                }
                if (k + l < 10 and match(C[0], char('0' + k)) and match(C[1], char('0' + l)) and
                    match(C[2], '-') and check(k + l)) {
                    ret += dp[N - 1][j][k][l];
                }
            }
        }
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int Q;
    std::cin >> Q;
    while (Q--) {
        int N;
        std::cin >> N;
        std::string S;
        std::cin >> S;
        vector<int> P(N);
        for (auto& x : P) {
            std::cin >> x;
        }
        std::cout << solve(N, S, P) << '\n';
    }
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 17 / 17
• Subtask 3: 26 / 26
• Subtask 4: 23 / 23
• Subtask 5: 18 / 18