Submission #1226394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226394		kaiboy	Bowling (BOI15_bow)	C++20	82 / 100	1092 ms	2028 KiB

bow

#include <algorithm>
#include <iostream>

using namespace std;

const  int   N = 10;
const  int   S = 300;
const  int   K = 13;
const char *AA = "0123456789x-/";

char aa[N * 2 + 2]; int ss[N];
long long dp[S + 1][K][K][2], dq[S + 1][K][K][2];

bool check(char a, char b) {
	if (a == 'x')
		return b == '-';
	if (!isdigit(a))
		return false;
	if (b == '/')
		return true;
	if (!isdigit(b))
		return false;
	return a - '0' + b - '0' < 10;
}

int geta(char a) {
	return a == 'x' ? 10 : a - '0';
}

int getb(char a, char b) {
	return b == 'x' ? 10 : b == '/' ? 10 - (a - '0') : b == '-' ? 0 : b - '0';
}

int calc(char a, char b) {
	return a == 'x' || b == '/' ? 10 : a - '0' + b - '0';
}

int count(char a, char b) {
	return a == 'x' ? 2 : b == '/' ? 1 : 0;
}

bool check(char a, char b, char c) {
	if (a == 'x' && b == 'x' && c == 'x')
		return true;
	if (a == 'x' && b == 'x')
		return isdigit(c);
	if (a == 'x' && c == '/')
		return isdigit(b);
	if (a == 'x')
		return isdigit(b) && isdigit(c) && b - '0' + c - '0' < 10;
	if (b == '/' && c == 'x')
		return isdigit(a);
	if (b == '/')
		return isdigit(a) && isdigit(c);
	return isdigit(a) && isdigit(b) && c == '-' && a - '0' + b - '0' < 10;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n >> aa;
		for (int i = 0; i < n; i++)
			cin >> ss[i];
		for (int s = 0; s <= S; s++)
			for (int ha = 0; ha < K; ha++)
				for (int hb = 0; hb < K; hb++)
					for (int f = 0; f <= 1; f++)
						dp[s][ha][hb][f] = 0;
		dp[0][0][0][0] = 1;
		for (int i = 0; i + 1 < n; i++) {
			for (int s = 0; s <= S; s++)
				for (int ha = 0; ha < K; ha++)
					for (int hb = 0; hb < K; hb++)
						for (int f = 0; f <= 1; f++)
							dq[s][ha][hb][f] = 0;
			char c_ = aa[i * 2], d_ = aa[i * 2 + 1];
			for (int s = 0; s <= S; s++)
				for (int ha = 0; ha < K; ha++)
					for (int hb = 0; hb < K; hb++)
						for (int f = 0; f <= 1; f++) {
							long long x = dp[s][ha][hb][f];
							if (x) {
								char a = AA[ha], b = AA[hb];
								for (int hc = 0; hc < K; hc++) {
									char c = AA[hc];
									if (c_ == '?' || c == c_)
										for (int hd = 0; hd < K; hd++) {
											char d = AA[hd];
											if ((d_ == '?' || d == d_) && check(c, d)) {
												int s_ = s + (f ? geta(c) : 0);
												if (i < 2 || ss[i - 2] == -1 || s_ == ss[i - 2]) {
													int t = s_ + calc(a, b), g = 0, k = count(a, b);
													if (k)
														t += geta(c);
													if (k >= 2)
														if (c == 'x')
															g = 1;
														else
															t += getb(c, d);
													dq[t][hc][hd][g] += x;
												}
											}
										}
								}
							}
						}
			for (int s = 0; s <= S; s++)
				for (int ha = 0; ha < K; ha++)
					for (int hb = 0; hb < K; hb++)
						for (int f = 0; f <= 1; f++)
							dp[s][ha][hb][f] = dq[s][ha][hb][f];
		}
		long long ans = 0;
		char c_ = aa[n * 2 - 2], d_ = aa[n * 2 - 1], e_ = aa[n * 2];
		for (int hc = 0; hc < K; hc++) {
			char c = AA[hc];
			if (c_ == '?' || c == c_)
				for (int hd = 0; hd < K; hd++) {
					char d = AA[hd];
					if (d_ == '?' || d == d_)
						for (int he = 0; he < K; he++) {
							char e = AA[he];
							if ((e_ == '?' || e == e_) && check(c, d, e))
								for (int s = 0; s <= S; s++)
									for (int ha = 0; ha < K; ha++)
										for (int hb = 0; hb < K; hb++)
											for (int f = 0; f <= 1; f++) {
												long long x = dp[s][ha][hb][f];
												if (x) {
													char a = AA[ha], b = AA[hb];
													int s_ = s + (f ? geta(c) : 0);
													if (n < 3 || ss[n - 3] == -1 || ss[n - 3] == s_) {
														int t = s_ + calc(a, b), k = count(a, b);
														if (k)
															t += geta(c);
														if (k >= 2)
															t += getb(c, d);
														if (ss[n - 2] == -1 || ss[n - 2] == t) {
															t += geta(c) + getb(c, d) + getb(d, e);
															if (ss[n - 1] == -1 || ss[n - 1] == t)
																ans += x;
														}
													}
												}
											}
						}
				}
		}
		cout << ans << '\n';
	}
	return 0;
}

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