제출 #1191254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191254		kl0989e	Bowling (BOI15_bow)	C++20	82 / 100	1018 ms	3488 KiB

bow

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

#pragma GCC optimize("Ofast")

#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, string lst) {
	string s="---";
	bool trd=0;
	if (a==10) {
		s[0]='x';
		trd=1;
	}
	else {
		s[0]='0'+a;
	}
	if (a==10 && b==10) {
		s[1]='x';
	}
	else if (a+b==10 && b!=0) {
		s[1]='/';
		trd=1;
	}
	else if (a+b<10 || a==10) {
		s[1]='0'+b;
	}
	else {
		return -1;
	}
	if (trd) {
		if (b==10 || (a+b==10 && b!=0)) {
			if (c==10) {
				s[2]='x';
			}
			else {
				s[2]='0'+c;
			}
		}
		else if (b+c==10) {
			s[2]='/';
		}
		else if (b+c<10) {
			s[2]='0'+c;
		}
		else {
			return -1;
		}
	}
	else if (c!=0) {
		return -1;
	}
	int n=sm.size();
	if ((lst[0]!='?' && lst[0]!=s[0]) || (lst[1]!='?' && lst[1]!=s[1]) || (lst[2]!='?' && lst[2]!=s[2])) {
		return -1;
	}
	if (sm[n-1]!=-1) {
		return sm[n-1]-a-b-c;
	}
	return -1e9;
}

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) {
		if (sco[2*i+1]==0 && !dash[2*i+1]) {
			return -1;
		}
		return s-a-a2-b2;
	}
	else if (a+b==10 && (sco[2*i+1]==-1 || sco[2*i+1]==11)) {
		return s-a-b-a2;
	}
	else if (a+b<10) {
		return s-a-b;
	}
	return -1;
}

ll dp[10][301][11][11];

void solve() {
	int n;
	cin >> n;
	vi sco(2*n+1);
	vi dash(2*n+1,0);
	vi strike(2*n+1,0);
	vi sm(n);
	string lst;
	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=='-';
		strike[i]=c=='x';
		if (i>=2*n-2) {
			lst+=c;
		}
	}
	for (int i=0; i<n; i++) {
		cin >> sm[i];
	}
	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,lst);
				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<=sco[2*i] && sco[2*i]<=10? sco[2*i]:0); j<=(0<=sco[2*i] && sco[2*i]<=10? sco[2*i]:10); j++) {
			for (int k=(0<=sco[2*i+1] && sco[2*i+1]<=10? sco[2*i+1]:0); k<=(0<=sco[2*i+1] && sco[2*i+1]<=10? sco[2*i+1]:10); k++) {
				for (int s=0; s<=(i+1)*30; s++) {
					for (int j2=(0<=sco[2*i+2] && sco[2*i+2]<=10? sco[2*i+2]:0); j2<=(0<=sco[2*i+2] && sco[2*i+2]<=10? sco[2*i+2]:10); 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: 16 / 16
• Subtask 2: 17 / 17
• Subtask 3: 26 / 26
• Subtask 4: 23 / 23
• Subtask 5: 0 / 18