Submission #49104

#	Time	Username	Problem	Language	Result	Execution time	Memory
49104		aome	Bowling (BOI15_bow)	C++17	100 / 100	113 ms	956 KiB

bow

#include <bits/stdc++.h>

using namespace std;

int n;
int score[10];
string s;
long long f[10][305][4];

void solve() {
	cin >> n >> s;
	for (int i = 0; i < n; ++i) cin >> score[i];
	memset(f, 0, sizeof f);

	// 0 -> i - 1 ko duoc 10
	// 1 -> i - 1 duoc 10
	// 2 -> i - 1 duoc strike
 	// 3 -> i - 1 duoc strike va i - 2 duoc strike

	f[0][0][0] = 1;

	for (int i = 0; i < (n - 1); ++i) {
		for (int j = 0; j <= 300; ++j) {
			for (int k = 0; k < 4; ++k) {
				if (!f[i][j][k]) continue;

				// cout << i << ' ' << j << ' ' << k << '\n';

				char c1 = s[i * 2], c2 = s[i * 2 + 1];

				for (int m1 = 0; m1 <= 10; ++m1) {
					if (c1 == 'x' || m1 == 10) {
						if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
					}
					else if (c1 != '?') {
						if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
					}

					for (int m2 = 0; m2 + m1 <= 10; ++m2) {
						if (c2 == '-' || m1 == 10) {
							if (m1 != 10 || c2 != '?' && c2 != '-') continue;
						}
						else if (c2 == '/' || m1 + m2 == 10) {
							if (m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
						}
						else if (c2 != '?') {
							if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
						}

						if (k == 0) {
							if (m1 == 10) {
								f[i + 1][j + 10][2] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								f[i + 1][j + 10][1] += f[i][j][k];
							}
							else {
								if (score[i] != -1 && score[i] != j + m1 + m2) continue;
								f[i + 1][j + m1 + m2][0] += f[i][j][k];
							}
						}

						if (k == 1) {
							if (m1 == 10) {
								if (score[i - 1] != -1 && score[i - 1] != j + 10) continue;
								f[i + 1][j + 10 + 10][2] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								if (score[i - 1] != -1 && score[i - 1] != j + m1) continue;
								f[i + 1][j + 10 + m1][1] += f[i][j][k];
							}
							else {
								if (score[i - 1] != -1 && score[i - 1] != j + m1) continue;
								if (score[i] != -1 && score[i] != j + m1 + m2 + m1) continue;
								f[i + 1][j + m1 + m2 + m1][0] += f[i][j][k];
							}
						}

						if (k == 2) {
							if (m1 == 10) {
								f[i + 1][j + 10][3] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								if (score[i - 1] != -1 && score[i - 1] != j + 10) continue;
								f[i + 1][j + 10 + 10][1] += f[i][j][k];
							}
							else {
								if (score[i - 1] != -1 && score[i - 1] != j + m1 + m2) continue;
								if (score[i] != -1 && score[i] != j + m1 + m2 + m1 + m2) continue;
								f[i + 1][j + m1 + m2 + m1 + m2][0] += f[i][j][k];
							}
						}

						if (k == 3) {
							if (m1 == 10) {
								if (score[i - 2] != -1 && score[i - 2] != (j - 10) + 10 + 10) continue;
								f[i + 1][j + 10 + 10 + 10][3] += f[i][j][k];
							}
							else if (m1 + m2 == 10) {
								if (score[i - 2] != -1 && score[i - 2] != (j - 10) + 10 + m1) continue;
								if (score[i - 1] != -1 && score[i - 1] != j + 10 + m1 + 10) continue;
								f[i + 1][j + 10 + m1 + 10 + 10][1] += f[i][j][k]; 
							}
							else {
								if (score[i - 2] != -1 && score[i - 2] != (j - 10) + 10 + m1) continue;
								if (score[i - 1] != -1 && score[i - 1] != j + 10 + m1 + m1 + m2) continue;
								if (score[i] != -1 && score[i] != j + 10 + m1 + m1 + m2 + m1 + m2) continue;
								f[i + 1][j + 10 + m1 + m1 + m2 + m1 + m2][0] += f[i][j][k];						
							}
						}
					}
				}
			}
		}
	}

	long long res = 0;

	for (int i = 0; i <= 300; ++i) {
		for (int j = 0; j < 4; ++j) {
			if (!f[n - 1][i][j]) continue;
			char c1 = s[(n - 1) * 2], c2 = s[(n - 1) * 2 + 1], c3 = s[(n - 1) * 2 + 2];

			// cout << i << ' ' << j << ' ' << f[n - 1][i][j] << '\n';

			for (int m1 = 0; m1 <= 10; ++m1) {
				if (c1 == 'x' || m1 == 10) {
					if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
				}
				else if (c1 != '?') {
					if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
				}

				// cout << m1 << '\n';

				int lim1 = 0;
				if (m1 == 10) lim1 = 10;
				else lim1 = 10 - m1;

				for (int m2 = 0; m2 <= lim1; ++m2) {
					if (c2 == 'x' || m1 == 10 && m2 == 10) {
						if (m1 != 10 || m2 != 10 || c2 != '?' && c2 != 'x') continue;
					}
					else if (c2 == '/' || m1 != 10 && m1 + m2 == 10) {
						if (m1 == 10 || m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
					}
					else if (c2 != '?') {
						if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
					}

					// cout << m1 << ' ' << m2 << '\n';

					int lim2 = 0;
					if (m1 == 10 && m2 == 10) lim2 = 10;
					else if (m1 == 10) lim2 = 10 - m2;
					else if (m1 + m2 == 10) lim2 = 10;

					for (int m3 = 0; m3 <= lim2; ++m3) {
						if (c3 == 'x' || ((m1 + m2 == 10 && m1 != 10) || m1 + m2 == 20) && m3 == 10) {
							if ((m1 + m2 != 10 || m1 == 10) && m1 + m2 != 20 || m3 != 10 || c3 != '?' && c3 != 'x') continue;
						}
						else if (c3 == '/' || m1 == 10 && m2 != 10 && m2 + m3 == 10) {
							if (m1 != 10 || m2 == 10 || m2 + m3 != 10 || c3 != '?' && c3 != '/') continue;
						}
						else if (c3 == '-' || m1 + m2 < 10) {
							if (m1 + m2 >= 10 || c3 != '?' && c3 != '-') continue;
						}
						else if (c3 != '?') {
							if (m3 != c3 - '0' || c3 != '?' && (c3 < '0' || c3 > '9')) continue;
						}

						// cout << m1 << ' ' << m2 << ' ' << m3 << '\n';

						if (j == 0) {
							if (score[n - 1] != -1 && i + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}

						if (j == 1) {
							if (score[n - 2] != -1 && i + m1 != score[n - 2]) continue;
							if (score[n - 1] != -1 && i + m1 + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}

						if (j == 2) {
							if (score[n - 2] != -1 && i + m1 + m2 != score[n - 2]) continue;
							if (score[n - 1] != -1 && i + m1 + m2 + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}

						if (j == 3) {
							if (score[n - 3] != -1 && (i - 10) + 10 + m1 != score[n - 3]) continue;
							if (score[n - 2] != -1 && i + 10 + m1 + m1 + m2 != score[n - 2]) continue;
							if (score[n - 1] != -1 && i + 10 + m1 + m1 + m2 + m1 + m2 + m3 != score[n - 1]) continue;
							res += f[n - 1][i][j];
						}
					}
				}
			}
		}
	}

	cout << res << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	int t; cin >> t; while (t--) solve();
}

Compilation message (stderr)

bow.cpp: In function 'void solve()':
bow.cpp:33:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
                       ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:36:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:41:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 != 10 || c2 != '?' && c2 != '-') continue;
                        ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:44:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
                             ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:47:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
                              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:128:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (m1 != 10 || c1 != '?' && c1 != 'x') continue;
                      ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:131:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (m1 != c1 - '0' || c1 != '?' && (c1 < '0' || c1 > '9')) continue;
                            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:141:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      if (c2 == 'x' || m1 == 10 && m2 == 10) {
                       ~~~~~~~~~^~~~~~~~~~~
bow.cpp:142:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 != 10 || m2 != 10 || c2 != '?' && c2 != 'x') continue;
                                   ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:144:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
      else if (c2 == '/' || m1 != 10 && m1 + m2 == 10) {
                            ~~~~~~~~~^~~~~~~~~~~~~~~~
bow.cpp:145:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m1 == 10 || m1 + m2 != 10 || c2 != '?' && c2 != '/') continue;
                                        ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:148:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (m2 != c2 - '0' || c2 != '?' && (c2 < '0' || c2 > '9')) continue;
                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bow.cpp:159:71: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       if (c3 == 'x' || ((m1 + m2 == 10 && m1 != 10) || m1 + m2 == 20) && m3 == 10) {
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
bow.cpp:160:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if ((m1 + m2 != 10 || m1 == 10) && m1 + m2 != 20 || m3 != 10 || c3 != '?' && c3 != 'x') continue;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
bow.cpp:160:82: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if ((m1 + m2 != 10 || m1 == 10) && m1 + m2 != 20 || m3 != 10 || c3 != '?' && c3 != 'x') continue;
                                                                        ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:162:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
       else if (c3 == '/' || m1 == 10 && m2 != 10 && m2 + m3 == 10) {
                             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
bow.cpp:163:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 != 10 || m2 == 10 || m2 + m3 != 10 || c3 != '?' && c3 != '/') continue;
                                                     ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:166:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m1 + m2 >= 10 || c3 != '?' && c3 != '-') continue;
                             ~~~~~~~~~~^~~~~~~~~~~~
bow.cpp:169:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
        if (m3 != c3 - '0' || c3 != '?' && (c3 < '0' || c3 > '9')) continue;
                              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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