Submission #1227785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227785		kaiboy	Bowling (BOI15_bow)	C++20	100 / 100	44 ms	328 KiB

bow

// coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const  int N = 10;
const  int S = 300;

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

bool check_s(int s, int i) {
	return i < 0 || ss[i] == -1 || s == ss[i];
}

bool check_a(char a, char a_) {
	return a_ == '?' || a == a_;
}

bool check_ab(int a, int b, char a_, char b_) {
	if (a + b < 10)
		return check_a(a + '0', a_) && check_a(b + '0', b_);
	if (a < 10)
		return check_a(a + '0', a_) && check_a('/', b_);
	return check_a('x', a_) && check_a('-', b_);
}

bool check_abc(int a, int b, int c, char a_, char b_, char c_) {
	if (a + b < 10)
		return check_a(a + '0', a_) && check_a(b + '0', b_) && check_a('-', c_);
	if (a < 10 && c < 10)
		return check_a(a + '0', a_) && check_a('/', b_) && check_a(c + '0', c_);
	if (a < 10)
		return check_a(a + '0', a_) && check_a('/', b_) && check_a('x', c_);
	if (b + c < 10)
		return check_a('x', a_) && check_a(b + '0', b_) && check_a(c + '0', c_);
	if (b < 10)
		return check_a('x', a_) && check_a(b + '0', b_) && check_a('/', c_);
	if (c < 10)
		return check_a('x', a_) && check_a('x', b_) && check_a(c + '0', c_);
	return check_a('x', a_) && check_a('x', b_) && check_a('x', c_);
}

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 y = 0; y < 4; y++)
			for (int s = 0; s <= S; s++)
				dp[y][s] = 0;
		dp[0][0] = 1;
		for (int i = 0; i + 1 < n; i++) {
			char a_ = aa[i * 2], b_ = aa[i * 2 + 1];
			for (int y = 0; y < 4; y++)
				for (int s = 0; s <= S; s++)
					dq[y][s] = 0;
			for (int y = 0; y < 4; y++)
				for (int s = 0; s <= S; s++) {
					long long x = dp[y][s];
					if (x) {
						for (int a = 0; a < 10; a++)
							for (int b = 0; a + b <= 10; b++)
								if (check_ab(a, b, a_, b_)) {
									int t = -1, z = a + b == 10;
									if (y == 0 && check_s(s, i - 1))
										t = s;
									else if (y == 1 && check_s(s + a, i - 1))
										t = s + a;
									else if (y == 2 && check_s(s + a + b, i - 1))
										t = s + a + b;
									else if (y == 3 && check_s(s - 10 + a, i - 2) && check_s(s + a + a + b, i - 1))
										t = s + a + a + b;
									if (t != -1)
										dq[z][t + a + b] += x;
								}
						if (check_ab(10, 0, a_, b_)) {
							int t = -1, z = -1;
							if (y == 0 && check_s(s, i - 1))
								t = s, z = 2;
							else if (y == 1 && check_s(s + 10, i - 1))
								t = s + 10, z = 2;
							else if (y == 2)
								t = s + 10, z = 3;
							else if (y == 3 && check_s(s, i - 2))
								t = s + 20, z = 3;
							if (t != -1)
								dq[z][t + 10] += x;
						}
					}
				}
			for (int y = 0; y < 4; y++)
				for (int s = 0; s <= S; s++)
					dp[y][s] = dq[y][s];
		}
		long long ans = 0;
		char a_ = aa[n * 2 - 2], b_ = aa[n * 2 - 1], c_ = aa[n * 2];
		for (int y = 0; y < 4; y++)
			for (int s = 0; s <= S; s++) {
				long long x = dp[y][s];
				if (x)
					for (int a = 0; a <= 10; a++)
						for (int b = a < 10 ? 10 - a : 10; b >= 0; b--)
							for (int c = a + b < 10 ? 0 : 10 - (a + b) % 10; c >= 0; c--)
								if (check_abc(a, b, c, a_, b_, c_)) {
									int t = -1;
									if (y == 0 && check_s(s, n - 2))
										t = s;
									else if (y == 1 && check_s(s + a, n - 2))
										t = s + a;
									else if (y == 2 && check_s(s + a + b, n - 2))
										t = s + a + b;
									else if (y == 3 && check_s(s - 10 + a, n - 3) && check_s(s + a + a + b, n - 2))
										t = s + a + a + b;
									if (t != -1 && check_s(t + a + b + c, n - 1))
										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: 18 / 18