Submission #727086

#TimeUsernameProblemLanguageResultExecution timeMemory
727086stasio6Bowling (BOI15_bow)C++14
0 / 100
1067 ms8772 KiB
#include <bits/stdc++.h> #define int long long 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]; int 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 <= 400; 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]; } } } } } } } int 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(); }
#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...