Submission #1111482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111482		Kirill22	Bowling (BOI15_bow)	C++17	100 / 100	562 ms	2636 KiB

bow

#include "bits/stdc++.h"
 
using namespace std;
 
const int N = 300;
long long dp[2][N][12][12];
 
void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        cin >> res[i];
    }
//    cin >> n;
//    s = string(2 * n + 1, '?');
//    vector<int> res(n, -1);
    int cur = 0;
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < 12; y++) {
            for (int z = 0; z < 12; z++) {
                dp[cur ^ 1][x][y][z] = dp[cur][x][y][z] = 0;
            }
        }
    }
    dp[cur][0][11][11] = 1;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
//        cout << i << endl;
//        cout << dp.size() << endl;
//        cout << (*dp.begin()).first[0] << " " << (*dp.rbegin()).first[0] << endl;
        vector<pair<array<int, 3>, long long>> dp2;
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < 12; y++) {
                for (int z = 0; z < 12; z++) {
                    dp[cur ^ 1][x][y][z] = 0;
                    if (dp[cur][x][y][z]) {
                        dp2.push_back({{x, y == 11 ? -1 : y, z == 11 ? -1 : z}, dp[cur][x][y][z]});
                    }
                }
            }
        }
        cur ^= 1;
//        dp2.clear();
//        if (i == 1) exit(0);
        if (i + 1 < n) {
            for (int x = 0; x <= 10; x++) {
                for (int y = 0; x + y <= 10; y++) {
                    string t = (string) "" + char('0' + x) + char('0' + y);
                    if (x == 10) {
                        t = "x-";
                    } else if (x + y == 10) {
                        t = (string) "" + char('0' + x) + '/';
                    }
                    if (s[i * 2] != '?' && s[i * 2] != t[0]) {
                        continue;
                    }
                    if (s[i * 2 + 1] != '?' && s[i * 2 + 1] != t[1]) {
                        continue;
                    }
                    if (t == "x-") {
                        for (auto& [_, cnt] : dp2) {
                            auto [sum, x1, x2] = _;
                            if (x1 != -1 && x1 != 10) continue;
                            for (int nsum = 0; nsum <= 30; nsum++) {
                                if (res[i] != -1 && res[i] != sum + nsum) continue;
                                for (int x3 = 0; x3 <= 10; x3++) {
                                    int x4 = nsum - 10 - x3;
                                    if (x4 >= 0 && x4 <= 10) {
                                        if (!(x2 != -1 && x2 != x3)) {
                                            dp[cur][sum + nsum][x3][x4] += cnt;
                                        }
                                    }
                                }
                            }
                        }
                    } else if (t[1] == '/') {
                        for (auto& [_, cnt] : dp2) {
                            auto [sum, x1, x2] = _;
                            if (x1 != -1 && x1 != x) continue;
                            if (x2 != -1 && x2 != y) continue;
                            for (int nsum = 10; nsum <= 20; nsum++) {
                                if (res[i] != -1 && res[i] != sum + nsum) continue;
                                dp[cur][sum + nsum][nsum - 10][11] += cnt;
                            }
                        }
                    } else {
                        for (auto& [_, cnt] : dp2) {
                            auto [sum, x1, x2] = _;
                            if (x1 != -1 && x1 != x) continue;
                            if (x2 != -1 && x2 != y) continue;
                            if (res[i] != -1 && res[i] != sum + x + y) continue;
                            dp[cur][sum + x + y][11][11] += cnt;
                        }
                    }
                }
            }
        } else {
            while ((int) s.size() > 3) {
                s.erase(s.begin());
            }
            for (int x = 0; x <= 10; x++) {
                for (int y = 0; y <= 10; y++) {
                    for (int z = 0; z <= 10; z++) {
                        if (x == 10 && y == 10 && z == 10) {
                            if (s[0] != '?' && s[0] != 'x') continue;
                            if (s[1] != '?' && s[1] != 'x') continue;
                            if (s[2] != '?' && s[2] != 'x') continue;
                            for (auto& [_, cnt] : dp2) {
                                auto [sum, x1, x2] = _;
                                if (x1 != -1 && x1 != x) continue;
                                if (x2 != -1 && x2 != y) continue;
                                if (res[i] != -1 && res[i] != sum + 30) continue;
                                ans += cnt;
                            }
                        } else if (x == 10 && y == 10) {
                            if (s[0] != '?' && s[0] != 'x') continue;
                            if (s[1] != '?' && s[1] != 'x') continue;
                            if (s[2] != '?' && s[2] != '0' + z) continue;
                            for (auto& [_, cnt] : dp2) {
                                auto [sum, x1, x2] = _;
                                if (x1 != -1 && x1 != x) continue;
                                if (x2 != -1 && x2 != y) continue;
                                if (res[i] != -1 && res[i] != sum + x + y + z) continue;
                                ans += cnt;
                            }
                        } else if (x == 10 && y + z == 10) {
                            if (s[0] != '?' && s[0] != 'x') continue;
                            if (s[1] != '?' && s[1] != '0' + y) continue;
                            if (s[2] != '?' && s[2] != '/') continue;
                            for (auto& [_, cnt] : dp2) {
                                auto [sum, x1, x2] = _;
                                if (x1 != -1 && x1 != x) continue;
                                if (x2 != -1 && x2 != y) continue;
                                if (res[i] != -1 && res[i] != sum + x + y + z) continue;
                                ans += cnt;
                            }
                        } else if (x == 10 && y + z < 10) {
                            if (s[0] != '?' && s[0] != 'x') continue;
                            if (s[1] != '?' && s[1] != '0' + y) continue;
                            if (s[2] != '?' && s[2] != '0' + z) continue;
                            for (auto& [_, cnt] : dp2) {
                                auto [sum, x1, x2] = _;
                                if (x1 != -1 && x1 != x) continue;
                                if (x2 != -1 && x2 != y) continue;
                                if (res[i] != -1 && res[i] != sum + x + y + z) continue;
                                ans += cnt;
                            }
                        } else if (x + y == 10 && z == 10) {
                            if (s[0] != '?' && s[0] != '0' + x) continue;
                            if (s[1] != '?' && s[1] != '/') continue;
                            if (s[2] != '?' && s[2] != 'x') continue;
                            for (auto& [_, cnt] : dp2) {
                                auto [sum, x1, x2] = _;
                                if (x1 != -1 && x1 != x) continue;
                                if (x2 != -1 && x2 != y) continue;
                                if (res[i] != -1 && res[i] != sum + x + y + z) continue;
                                ans += cnt;
                            }
                        } else if (x + y == 10 && z < 10) {
                            if (s[0] != '?' && s[0] != '0' + x) continue;
                            if (s[1] != '?' && s[1] != '/') continue;
                            if (s[2] != '?' && s[2] != '0' + z) continue;
                            for (auto& [_, cnt] : dp2) {
                                auto [sum, x1, x2] = _;
                                if (x1 != -1 && x1 != x) continue;
                                if (x2 != -1 && x2 != y) continue;
                                if (res[i] != -1 && res[i] != sum + x + y + z) continue;
                                ans += cnt;
                            }
                        } else if (x + y < 10 && z == 0) {
                            if (s[0] != '?' && s[0] != '0' + x) continue;
                            if (s[1] != '?' && s[1] != '0' + y) continue;
                            if (s[2] != '?' && s[2] != '-') continue;
                            for (auto& [_, cnt] : dp2) {
                                auto [sum, x1, x2] = _;
                                if (x1 != -1 && x1 != x) continue;
                                if (x2 != -1 && x2 != y) continue;
                                if (res[i] != -1 && res[i] != sum + x + y + z) continue;
                                ans += cnt;
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

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