Submission #1190368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190368		kl0989e	Bowling (BOI15_bow)	C++20	0 / 100	1096 ms	3280 KiB

bow

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

int parse(int a, int b, int c, vi& sm, vi& sco, vi& dash) {
	int n=sm.size();
	if ((sco[2*n-2]!=-1 && sco[2*n-2]!=a) || (sco[2*n-1]!=-1 && sco[2*n-1]!=b && sco[2*n-1]!=11) || (sco[2*n]!=-1 && sco[2*n]!=c && sco[2*n]!=11)) {
		return -1;
	}
	if (dash[2*n]) {
		if (c==0 && a+b<10) {
			if (sm[n-1]!=-1) {
				return sm[n-1]-a-b-c;
			}
			return -1e9;
		}
		return -1;
	}
	if (sco[2*n]==11 && sco[2*n+1]==11) {
		return -1;
	}
	if (sco[2*n]==11) {
		if (a+b==10 && b!=0) {
			if (sm[n-1]!=-1) {
				return sm[n-1]-a-b-c;
			}
			return -1e9;
		}
		return -1;
	}
	else if (sco[2*n+1]==11) {
		if (a==10 && b+c==10 && c!=0) {
			return sm[n-1]-a-b-c;
		}
		return -1e9;
	}
	if (a==10) {
		if (b==10) {
			if (sm[n-1]!=-1) {
				return sm[n-1]-a-b-c;
			}
			return -1e9;
		}
		else if (b+c<=10) {
			if (sm[n-1]!=-1) {
				return sm[n-1]-a-b-c;
			}
			return -1e9;
		}
	}
	else if (a+b==10) {
		if (sm[n-1]!=-1) {
			return sm[n-1]-a-b-c;
		}
		return -1e9;
	}
	else if (a+b<10 && c==0) {
		if (sm[n-1]!=-1) {
			return sm[n-1]-a-b-c;
		}
		return -1e9;
	}
	return -1;
}

int parse2(int i, int a, int b, int s, int a2, int b2, vi& sm, vi& sco, vi& dash) {
	int n=sm.size();
	if ((sco[2*i]!=-1 && sco[2*i]!=a) || (sco[2*i+1]!=-1 && sco[2*i+1]!=b && sco[2*i+1]!=11)) {
		return -1;
	}
	if (sco[2*i+1]==11) {
		if (a+b==10 && b!=0) {
			return s-a-b-a2;
		}
		return -1;
	}
	if (dash[2*i+1]) {
		if (a==10 && b==0) {
			return s-a-a2-b2;
		}
		return -1;
	}
	if (a==10 && b==0) {
		return s-a-a2-b2;
	}
	else if (a+b==10) {
		return s-a-b-a2;
	}
	else if (a+b<10) {
		return s-a-b;
	}
	return -1;
}

void solve() {
	int n;
	cin >> n;
	vi sco(2*n+1);
	vi dash(2*n+1,0);
	vi sm(n);
	char c;
	for (int i=0; i<2*n+1; i++) {
		cin >> c;
		if (c=='?') {
			sco[i]=-1;
		}
		else if (c=='/') {
			sco[i]=11;
		}
		else if (c=='-') {
			sco[i]=0;
		}
		else if (c=='x') {
			sco[i]=10;
		}
		else {
			sco[i]=c-'0';
		}
		dash[i]=c=='-';
	}
	for (int i=0; i<n; i++) {
		cin >> sm[i];
	}
	ll dp[n][30*n+1][11][11];
	memset(dp,0,sizeof(dp));
	for (int i=0; i<11; i++) {
		for (int j=0; j<11; j++) {
			for (int k=0; k<11; k++) {
				int t=parse(i,j,k,sm,sco,dash);
				if (t==-1e9) {
					for (int l=0; l<=30*n; l++) {
						if (n!=1 && l!=sm[n-2] && sm[n-2]!=-1) {
							continue;
						}
						dp[n-1][l][i][j]++;
					}
				}
				else if (t>=0) {
					if (n!=1 && t!=sm[n-2] && sm[n-2]!=-1) {
						continue;
					}
					dp[n-1][t][i][j]++;
				}
			}
		}
	}
	for (int i=n-2; i>=0; i--) {
		for (int j=0; j<11; j++) {
			for (int k=0; k<11; k++) {
				for (int s=0; s<=30*n; s++) {
					for (int j2=0; j2<11; j2++) {
						for (int k2=0; k2<11; k2++) {
							int t=parse2(i,j,k,s,j2,k2,sm,sco,dash);
							if (i!=0 && t!=sm[i-1] && sm[i-1]!=-1) {
								continue;
							}
							if (t>=0) {
								if (j==10) {
									dp[i][t][j][j2]+=dp[i+1][s][j2][k2];
								}
								else {
									dp[i][t][j][k]+=dp[i+1][s][j2][k2];
								}
							}
						}
					}
				}
			}
		}
	}
	ll ans=0;
	for (int i=0; i<11; i++) {
		for (int j=0; j<11; j++) {
			ans+=dp[0][0][i][j];
		}
	}
	cout << ans << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

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