oj.uz

답안 #891115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891115 2023-12-22T07:56:01 Z shiomusubi496 Bowling (BOI15_bow) C++17
0 / 100
 42 ms 4700 KB 
#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))));
    // dp[i][j][k][l] : i までやって現在の得点が j で、次の二回の shot で k, l 本倒す方法の数
    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 (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 + 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
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -