Submission #1227779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227779		kaiboy	Bowling (BOI15_bow)	C++20	100 / 100	39 ms	456 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[S + 1][4], dq[S + 1][4];

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