oj.uz

Submission #727093

# Submission time Handle Problem Language Result Execution time Memory
727093 2023-04-20T03:45:36 Z stasio6 Bowling (BOI15_bow) C++14
23 / 100
 471 ms 8780 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FI first
#define ND second
#define maxeq(x, y) (x) = max((x), (y))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int score[20];

const int maxFrameScore[11] = {0, 10, 30, 60, 90, 120, 150, 180, 210, 240, 300};
ll dp[15][500][12][12];
string game;

bool cmp(int i, char c1, char c2) {
    return (game[2*(i-1)] == '?' || game[2*(i-1)] == c1) && (game[2*(i-1)+1] == '?' || game[2*(i-1)+1] == c2);
}

void fun() {
    int n;
    cin >> n;
    cin >> game;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    for (int i = 0; i < 15; i++)
        for (int s = 0; s < 500; s++)
            for (int p = 0; p <= 10; p++)
                for (int d = 0; d <= 10; d++)
                    dp[i][s][p][d] = 0;
    for (int p = 0; p <= 10; p++) {
        for (int d = 0; d <= 10; d++) {
            dp[0][0][p][d] = 1;
        }
    }
    for (int i = 1; i < n; i++) {
        for (int s = 0; s <= maxFrameScore[i] + 30; s++) {
            if (score[i] != -1 && score[i] != s)
                continue;
            for (int p = 0; p <= 10; p++) {
                for (int d = 0; d <= 10; d++) {
                    // Strike
                    if (s >= 10 + d + p && cmp(i, 'x', '-'))
                        dp[i][s][p][d] += dp[i-1][s - 10 - p - d][10][p];
                    for (int r1 = 0; r1 < 10; r1++) {
                        for (int r2 = 0; r2 <= 10 - r1; r2++) {
                            if (r1+r2 == 10) {
                                if (!cmp(i, '0'+r1, '/'))
                                    continue;
                                if (s >= r1 + r2 + p)
                                    dp[i][s][p][d] += dp[i-1][s - r1 - r2 - p][r1][r2];
                            } else {
                                if (!cmp(i, '0'+r1, '0'+r2))
                                    continue;
                                if (s >= r1 + r2)
                                    dp[i][s][p][d] += dp[i-1][s - r1 - r2][r1][r2];
                            }
                        }
                    }
                }
            }
        }
    }
    ll ile = 0;
    for (int s = 0; s <= 400; s++) {
        ile += dp[n - 1][s][0][0];
    }
    cout << ile << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) fun();
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 8756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 8756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 8752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 8660 KB Output is correct
2 Correct 226 ms 8760 KB Output is correct
3 Correct 259 ms 8660 KB Output is correct
4 Correct 210 ms 8660 KB Output is correct
5 Correct 255 ms 8652 KB Output is correct
6 Correct 202 ms 8660 KB Output is correct
7 Correct 183 ms 8756 KB Output is correct
8 Correct 191 ms 8760 KB Output is correct
9 Correct 229 ms 8764 KB Output is correct
10 Correct 407 ms 8780 KB Output is correct
11 Correct 404 ms 8756 KB Output is correct
12 Correct 368 ms 8756 KB Output is correct
13 Correct 342 ms 8760 KB Output is correct
14 Correct 471 ms 8756 KB Output is correct
15 Correct 402 ms 8760 KB Output is correct
16 Correct 415 ms 8660 KB Output is correct
17 Correct 438 ms 8760 KB Output is correct
18 Correct 329 ms 8768 KB Output is correct
19 Correct 353 ms 8760 KB Output is correct
20 Correct 381 ms 8760 KB Output is correct
21 Correct 374 ms 8764 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 8756 KB Output isn't correct
2 Halted 0 ms 0 KB -