Submission #1227730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227730		kaiboy	Bowling (BOI15_bow)	C++20	100 / 100	544 ms	2164 KiB

bow

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

vector<pair<int, int>> qu2;
vector<tuple<int, int, int>> qu3;
int aa[K], bb[K][K], xx[K][K], kk[K][K];

bool check(int a, int b) {
	a = AA[a], b = AA[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(int a) {
	a = AA[a];
	return a == 'x' ? 10 : a - '0';
}

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

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

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

bool check(int a, int b, int c) {
	a = AA[a], b = AA[b], c = AA[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 decode(int a_) {
	if (a_ == '?')
		return -1;
	int a = 0;
	while (AA[a] != a_)
		a++;
	return a;
}

void init() {
	for (int a = 0; a < K; a++) {
		aa[a] = geta(a);
		for (int b = 0; b < K; b++) {
			if (check(a, b))
				qu2.push_back({ a, b });
			bb[a][b] = getb(a, b);
			xx[a][b] = calc(a, b);
			kk[a][b] = count(a, b);
			for (int c = 0; c < K; c++)
				if (check(a, b, c))
					qu3.push_back({ a, b, c });
		}
	}
}

char aa_[N * 2 + 2]; int ss[N];
long long dp[K][K][S + 1][2], dq[K][K][S + 1][2];
vector<tuple<int, int, int, int>> *qu, *qu_;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	init();
	int t; cin >> t;
	qu = new vector<tuple<int, int, int, int>>;
	qu_ = new vector<tuple<int, int, int, int>>;
	while (t--) {
		int n; cin >> n >> aa_;
		for (int i = 0; i < n; i++)
			cin >> ss[i];
		for (int i = 0; i <= n * 2; i++)
			aa_[i] = decode(aa_[i]);
		for (int a = 0; a < K; a++)
			for (int b = 0; b < K; b++)
				for (int s = 0; s <= S; s++)
					for (int f = 0; f <= 1; f++)
						dp[a][b][s][f] = 0;
		qu->clear();
		qu->push_back({ 0, 0, 0, 0 });
		dp[0][0][0][0] = 1;
		for (int i = 0; i + 1 < n; i++) {
			int c_ = aa_[i * 2], d_ = aa_[i * 2 + 1];
			for (auto &cd : qu2) {
				int c = cd.first, d = cd.second;
				if ((c_ == -1 || c == c_) && (d_ == -1 || d == d_))
					for (auto &z : *qu) {
						int a = get<0>(z), b = get<1>(z), s = get<2>(z), f = get<3>(z);
						long long x = dp[a][b][s][f];
						int s_ = s + (f ? aa[c] : 0);
						if (i < 2 || ss[i - 2] == -1 || s_ == ss[i - 2]) {
							int t = s_ + xx[a][b], g = 0, k = kk[a][b];
							if (k)
								t += aa[c];
							if (k >= 2)
								if (AA[c] == 'x')
									g = 1;
								else
									t += bb[c][d];
							if (!dq[c][d][t][g])
								qu_->push_back({ c, d, t, g });
							dq[c][d][t][g] += x;
						}
					}
			}
			for (auto &z : *qu_) {
				int a = get<0>(z), b = get<1>(z), s = get<2>(z), f = get<3>(z);
				dp[a][b][s][f] = dq[a][b][s][f], dq[a][b][s][f] = 0;
			}
			swap(qu, qu_), qu_->clear();
		}
		long long ans = 0;
		int c_ = aa_[n * 2 - 2], d_ = aa_[n * 2 - 1], e_ = aa_[n * 2];
		for (auto &cde : qu3) {
			int c = get<0>(cde), d = get<1>(cde), e = get<2>(cde);
			if ((c_ == -1 || c == c_) && (d_ == -1 || d == d_) && (e_ == -1 || e == e_))
				for (auto &z : *qu) {
					int a = get<0>(z), b = get<1>(z), s = get<2>(z), f = get<3>(z);
					long long x = dp[a][b][s][f];
					int s_ = s + (f ? aa[c] : 0);
					if (n < 3 || ss[n - 3] == -1 || ss[n - 3] == s_) {
						int t = s_ + xx[a][b], k = kk[a][b];
						if (k)
							t += aa[c];
						if (k >= 2)
							t += bb[c][d];
						if (ss[n - 2] == -1 || ss[n - 2] == t) {
							t += aa[c] + bb[c][d] + bb[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: 18 / 18