Submission #891141

#	Time	Username	Problem	Language	Result	Execution time	Memory
891141		shiomusubi496	Bowling (BOI15_bow)	C++17	100 / 100	153 ms	4956 KiB

bow

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define all(v) begin(v), end(v)

using ll = long long;

void solve();

int main() {
    int q; cin >> q;
    rep (_, q) solve();
}

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> a(n);
    rep (i, n) cin >> a[i];
    vector dp(n, vector(301, vector(11, vector(11, 0ll))));
    rep (i, 11) rep (j, 11) dp[0][0][i][j] = 1;
    rep (i, n - 1) {
        string t = s.substr(i * 2, 2);
        rep (j, 301) rep (k, 11) rep (l, 11) {
            if (dp[i][j][k][l] == 0) continue;
            if (k == 10) {
                if ((t[0] == 'x' || t[0] == '?') && (t[1] == '-' || t[1] == '?')) {
                    rep (m, 11) {
                        if (a[i] == -1 || a[i] == j + 10 + l + m) dp[i + 1][j + 10 + l + m][l][m] += dp[i][j][k][l];
                    }
                }
            }
            else if (k + l <= 10) {
                if (t[0] == 'x' || t[1] == '-') continue;
                if (k + l == 10) {
                    if (t[1] == '/' || t[1] == '?') {
                        if (t[0] != '?' && t[0] - '0' != k) continue;
                        rep (m, 11) {
                            if (a[i] == -1 || a[i] == j + 10 + m) {
                                rep (n, 11) dp[i + 1][j + 10 + m][m][n] += dp[i][j][k][l];
                            }
                        }
                    }
                }
                else {
                    if (t[1] == '/') continue;
                    if (t[0] != '?' && t[0] - '0' != k) continue;
                    if (t[1] != '?' && t[1] - '0' != l) continue;
                    if (a[i] == -1 || a[i] == j + k + l) {
                        rep (m, 11) rep (n, 11) dp[i + 1][j + k + l][m][n] += dp[i][j][k][l];
                    }
                }
            }
        }
    }
    ll ans = 0;
    string t = s.substr((n - 1) * 2);
    rep (s, 301) {
        do {
            if (t[0] != '?' && t[0] != 'x') continue;
            if (t[1] != '?' && t[1] != 'x') continue;
            if (t[2] != '?' && t[2] != 'x') continue;
            if (a[n - 1] == -1 || a[n - 1] == s + 30) ans += dp[n - 1][s][10][10];
        } while (0);
        rep (i, 10) {
            if (t[0] != '?' && t[0] != 'x') continue;
            if (t[1] != '?' && t[1] != 'x') continue;
            if (t[2] != '?' && t[2] - '0' != i) continue;
            if (a[n - 1] == -1 || a[n - 1] == s + 20 + i) ans += dp[n - 1][s][10][10];
        }
        rep (i, 10) {
            if (t[0] != '?' && t[0] != 'x') continue;
            if (t[1] != '?' && t[1] - '0' != i) continue;
            if (t[2] != '?' && t[2] != '/') continue;
            if (a[n - 1] == -1 || a[n - 1] == s + 20) ans += dp[n - 1][s][10][i];
        }
        rep (i, 10) rep (j, 10) {
            if (i + j >= 10) break;
            if (t[0] != '?' && t[0] != 'x') continue;
            if (t[1] != '?' && t[1] - '0' != i) continue;
            if (t[2] != '?' && t[2] - '0' != j) continue;
            if (a[n - 1] == -1 || a[n - 1] == s + 10 + i + j) ans += dp[n - 1][s][10][i];
        }
        rep (i, 10) {
            if (t[0] != '?' && t[0] - '0' != i) continue;
            if (t[1] != '?' && t[1] != '/') continue;
            if (t[2] != '?' && t[2] != 'x') continue;
            if (a[n - 1] == -1 || a[n - 1] == s + 20) ans += dp[n - 1][s][i][10 - i];
        }
        rep (i, 10) rep (j, 10) {
            if (t[0] != '?' && t[0] - '0' != i) continue;
            if (t[1] != '?' && t[1] != '/') continue;
            if (t[2] != '?' && t[2] - '0' != j) continue;
            if (a[n - 1] == -1 || a[n - 1] == s + 10 + j) ans += dp[n - 1][s][i][10 - i];
        }
        rep (i, 10) rep (j, 10) {
            if (i + j >= 10) break;
            if (t[0] != '?' && t[0] - '0' != i) continue;
            if (t[1] != '?' && t[1] - '0' != j) continue;
            if (t[2] != '?' && t[2] != '-') continue;
            if (a[n - 1] == -1 || a[n - 1] == s + i + j) ans += dp[n - 1][s][i][j];
        }
    }
    cout << ans << endl;
}

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