Submission #127758

#	Time	Username	Problem	Language	Result	Execution time	Memory
127758		tmwilliamlin168	Bowling (BOI15_bow)	C++14	82 / 100	1018 ms	3708 KiB

bow

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

#define ll long long

const int mxN=10;
int q, n, a[mxN];
string s;
ll dp[mxN+1][301][11][11], dp2[mxN+1][301];

struct frame {
	vector<int> v;
	int b1, b2;
	string s;
};
vector<frame> vs, vf;

void solve() {
	cin >> n >> s;
	for(int i=0; i<n; ++i)
		cin >> a[i];
	memset(dp, 0, sizeof(dp));
	memset(dp2, 0, sizeof(dp2));
	dp2[0][0]=1;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<=300; ++j) {
			for(int k=0; k<=10; ++k)
				for(int l=0; l<=10; ++l)
					dp[i][j][k][l]+=dp2[i][j];
			for(frame f : (i<n-1?vs:vf)) {
				bool ok=1;
				for(int k=0; k<f.s.size()&&ok; ++k)
					ok=s[2*i+k]=='?'||s[2*i+k]==f.s[k];
				if(!ok)
					continue;
				int bs=j;
				for(int b : f.v)
					bs+=b;
				for(int k=0; k<=10; ++k) {
					if(k^f.v[0])
						continue;
					for(int l=0; l<=10; ++l) {
						if((f.v.size()>1&&l^f.v[1])||!dp[i][j][k][l])
							continue;
						if(f.b1||f.b2||f.v.size()<2||~a[i]) {
							for(int k2=0; k2<=10; ++k2) {
								if(f.v.size()<2&&k2^l)
									continue;
								for(int l2=0; l2<=10; ++l2) {
									int j2=bs+f.b1*k2+f.b2*l2;
									if(a[i]<0||a[i]==j2)
										dp[i+1][j2][k2][l2]+=dp[i][j][k][l];
								}
							}
						} else
							dp2[i+1][bs]+=dp[i][j][k][l];
					}
				}
			}
		}
	}
	ll ans=0;
	for(int i=0; i<=300; ++i)
		ans+=dp[n][i][0][0]+dp2[n][i];
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	vs.push_back({{10}, 1, 1, "x-"});
	for(int i=0; i<10; ++i)
		vs.push_back({{i, 10-i}, 1, 0, to_string(i)+"/"});
	for(int i=0; i<10; ++i)
		for(int j=0; j<10-i; ++j)
			vs.push_back({{i, j}, 0, 0, to_string(i)+to_string(j)});
	vf.push_back({{10, 10, 10}, 0, 0, "xxx"});
	for(int i=0; i<10; ++i)
		vf.push_back({{10, 10, i}, 0, 0, "xx"+to_string(i)});
	for(int i=0; i<10; ++i)
		vf.push_back({{10, i, 10-i}, 0, 0, "x"+to_string(i)+"/"});
	for(int i=0; i<10; ++i)
		for(int j=0; j<10-i; ++j)
			vf.push_back({{10, i, j}, 0, 0, "x"+to_string(i)+to_string(j)});
	for(int i=0; i<10; ++i)
		vf.push_back({{i, 10-i, 10}, 0, 0, to_string(i)+"/x"});
	for(int i=0; i<10; ++i)
		for(int j=0; j<10; ++j)
			vf.push_back({{i, 10-i, j}, 0, 0, to_string(i)+"/"+to_string(j)});
	for(int i=0; i<10; ++i)
		for(int j=0; j<10-i; ++j)
			vf.push_back({{i, j}, 0, 0, to_string(i)+to_string(j)+"-"});
	cin >> q;
	while(q--)
		solve();
}

Compilation message (stderr)

bow.cpp: In function 'void solve()':
bow.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0; k<f.s.size()&&ok; ++k)
                  ~^~~~~~~~~~~

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