Submission #727166

#TimeUsernameProblemLanguageResultExecution timeMemory
727166stasio6Bowling (BOI15_bow)C++14
0 / 100
14 ms468 KiB
#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; const int maxFrameScore[11] = {0, 10, 30, 60, 90, 120, 150, 180, 210, 240, 300}; int score[20]; ll dp[15][500][4]; 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); } bool scorecmp(int i, int s) { return score[i] == -1 || score[i] == s; } void fun() { int n; cin >> n; cin >> game; 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 st = 0; st < 3; st++) dp[i][s][st]= 0; dp[0][0][0] = 1; for (int i = 1; i < n; i++) { for (int s = 0; s <= maxFrameScore[i]+30; s++) { // Strike if (cmp(i, 'x', '-')) { // no strikes if (s >= 10 && scorecmp(i-1, s-10)) dp[i][s][2] += dp[i - 1][s - 10][0]; // spare if (s >= 20 && scorecmp(i-1, s-10)) dp[i][s][2] += dp[i - 1][s - 20][1]; // strike if (s >= 20) dp[i][s][3] += dp[i - 1][s - 20][2]; // double strike if (s >= 30 && i > 2 && scorecmp(i - 2, s - 30)) dp[i][s][3] += dp[i - 1][s - 30][3]; } for (int r1 = 0; r1 < 10; r1++) { for (int r2 = 0; r2 <= 10 - r1; r2++) { int spare = 0; if (r1 + r2 == 10) { if (!cmp(i, '0' + r1, '/')) continue; spare = 1; } else { if (!cmp(i, '0' + r1, '0' + r2)) continue; } // no strikes if (s >= r1 + r2 && scorecmp(i-1, s-r1-r2)) dp[i][s][spare] += dp[i - 1][s - r1 - r2][0]; // spare if (s >= 2*r1 + r2 && scorecmp(i-1, s-r1-r2)) dp[i][s][spare] += dp[i - 1][s - 2*r1-r2][1]; // strike if (s >= 2*(r1+r2) && scorecmp(i-1, s-r1-r2)) dp[i][s][spare] += dp[i - 1][s - 2*(r1+r2)][2]; // double strike if (s >= 3*r1+2*r2 && i > 2 && scorecmp(i - 2, s - 10 - 2*(r1+r2)) && scorecmp(i-1, s-r1-r2)) dp[i][s][spare] += dp[i - 1][s - 3*r1-2*r2][3]; } } } } // Ostatnia runda ll ile = 0; for (int s = 0; s <= 400; s++) { if (!scorecmp(n, s)) continue; // 3 striki lub 2 striki cos for (int t = 0; t <= 10; t++) { if (!cmp(n, 'x', 'x') || !cmp(n+1, t == 10 ? 'x' : '0'+t, '?')) continue; // no strikes if (s >= 20+t && scorecmp(n-1, s-20-t)) ile += dp[n - 1][s - 20 - t][0]; // spare if (s >= 30+t && scorecmp(n-1, s-20-t)) ile += dp[n - 1][s - 30 - t][1]; // strike if (s >= 40+t && scorecmp(n-1, s - 20-t)) ile += dp[n - 1][s - 40 - t][2]; // double strike if (s >= 50+t && n > 2 && scorecmp(n-1, s - 20 - t) && scorecmp(n-2, s - 50 - t)) ile += dp[n - 1][s - 50 - t][3]; } // strike cos for (int p = 0; p < 10; p++) { for (int d = 0; d <= 10 - p; d++) { if (!cmp(n, 'x', '0'+p) || !cmp(n+1, p+d == 10 ? '/' : '0'+d, '?')) continue; // no strikes if (s >= 10+p+d && scorecmp(n-1, s-10-p-d)) ile += dp[n - 1][s - 10 - p - d][0]; // spare if (s >= 20+p+d && scorecmp(n-1, s-10-p-d)) ile += dp[n - 1][s - 20 - p - d][1]; // strike if (s >= 20+2*p+d && scorecmp(n-1, s - 10 - p - d)) ile += dp[n - 1][s - 20 - 2*p-d][2]; // double strike if (s >= 30+2*p+d && n > 2 && scorecmp(n-1, s - 10 - p - d) && scorecmp(n-2, s - 30 - 2*p - d)) ile += dp[n - 1][s - 30 - 2*p-d][3]; } } // spare cos for (int p = 0; p < 10; p++) { for (int d = 0; d <= 10; d++) { if (!cmp(n, '0'+p, '/') || !cmp(n+1, d == 10 ? 'x' : '0'+d, '?')) continue; // no strikes if (s >= 10+d && scorecmp(n-1, s-10-d)) ile += dp[n - 1][s - 10 - d][0]; // spare if (s >= 10+p+d && scorecmp(n-1, s-10-d)) ile += dp[n - 1][s - 10 - p - d][1]; // strike if (s >= 20+d && scorecmp(n-1, s - 10 - d)) ile += dp[n - 1][s - 20 -d][2]; // double strike if (s >= 20+p+d && n > 2 && scorecmp(n-1, s - 10 - d) && scorecmp(n-2, s - 30 - d)) ile += dp[n - 1][s - 20 - p-d][3]; } } // cos for (int p = 0; p < 10; p++) { for (int d = 0; d < 10-p; d++) { if (!cmp(n, '0'+p, '0'+d) || !cmp(n+1, '-', '?')) continue; // no strikes if (s >= p+d && scorecmp(n-1, s-p-d)) ile += dp[n - 1][s - p - d][0]; // spare if (s >= 2*p+d && scorecmp(n-1, s-p-d)) ile += dp[n - 1][s - 2*p - d][1]; // strike if (s >= 2*(p+d) && scorecmp(n-1, s - p - d)) ile += dp[n - 1][s - 2*(p+d)][2]; // double strike if (s >= 3*p+2*d && n > 2 && scorecmp(n-1, s - p - d) && scorecmp(n-2, s - 10 - 2*p-2*d)) ile += dp[n - 1][s - 3*p-2*d][3]; } } } cout << ile << "\n"; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) fun(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...