Submission #563780

#	Time	Username	Problem	Language	Result	Execution time	Memory
563780		KoD	Bowling (BOI15_bow)	C++17	100 / 100	195 ms	3540 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;
using std::array;
using std::pair;
using std::tuple;

template <class T> constexpr T infty = std::numeric_limits<T>::max() / 2;

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(round, N - 1) rep(point, 331) rep(k, 11) rep(l, 11) {
        const ll val = dp[round][point][k][l];
        if (val == 0) continue;

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

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

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