Submission #120001

#	Time	Username	Problem	Language	Result	Execution time	Memory
120001		E869120	Bowling (BOI15_bow)	C++14	100 / 100	587 ms	5376 KiB

bow

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
using namespace std;

long long dp[12][12][12][360];
vector<tuple<string, int, int, int>> bnormal, blast;

void init() {
	for (int i = 0; i <= 10; i++) {
		for (int j = 0; j <= 10 - i; j++) {
			string V = "";
			if (i == 10) V = "x-";
			else if (i + j == 10) V = to_string(i) + "/";
			else V = to_string(i) + to_string(j);
			bnormal.push_back(make_tuple(V, i, j, 0));
		}
	}
	for (int i = 0; i <= 10; i++) {
		for (int j = 0; j <= 10; j++) {
			for (int k = 0; k <= 10; k++) {
				if (i + j > 10 && i != 10) continue;
				if (i == 10) {
					if (j + k > 10 && j != 10) continue;
				}
				if (i + j < 10 && k >= 1) continue;

				string V = "";
				if (i == 10 && j == 10 && k == 10) V = "xxx";
				else if (i == 10 && j == 10) V = "xx" + to_string(k);
				else if (i == 10 && j + k == 10) V = "x" + to_string(j) + "/";
				else if (i == 10) V = "x" + to_string(j) + to_string(k);
				else if (i + j == 10 && k == 10) V += to_string(i) + "/x";
				else if (i + j == 10) V += to_string(i) + "/" + to_string(k);
				else V += to_string(i) + to_string(j) + "-";
				blast.push_back(make_tuple(V, i, j, k));
			}
		}
	}
	sort(bnormal.begin(), bnormal.end()); bnormal.erase(unique(bnormal.begin(), bnormal.end()), bnormal.end());
	sort(blast.begin(), blast.end()); blast.erase(unique(blast.begin(), blast.end()), blast.end());
	return;
}

long long solve(string S, vector<int>vec) {
	for (int i = 0; i < 12 * 12; i++) {
		for (int j = 0; j < 12 * 360; j++) dp[i / 12][i % 12][j / 360][j % 360] = 0;
	}
	for (int i = 0; i < blast.size(); i++) {
		bool flag = true;
		for (int j = 0; j < 3; j++) { if (S[j + (int)(vec.size() - 1) * 2] != '?' && S[j + (int)(vec.size() - 1) * 2] != get<0>(blast[i])[j]) flag = false; }
		if (flag == true) {
			for (int j = 0; j <= 330; j++) {
				if (vec[vec.size() - 1] != -1 && vec[vec.size() - 1] != j) continue;
				int G1 = get<1>(blast[i]) + get<2>(blast[i]) + get<3>(blast[i]);
				if (j >= G1) {
					dp[vec.size() - 1][get<1>(blast[i])][get<2>(blast[i])][j - G1] += 1;
				}
			}
		}
	}
	for (int i = (int)vec.size() - 2; i >= 0; i--) {
		for (int j = 0; j <= 10; j++) {
			for (int k = 0; k <= 10; k++) {
				for (int l = 0; l <= 330; l++) {
					if (vec[i] != -1 && l != vec[i]) dp[i + 1][j][k][l] = 0;
					if (dp[i + 1][j][k][l] == 0) continue;

					for (int m = 0; m < bnormal.size(); m++) {
						bool flag = true;
						for (int n = 0; n < 2; n++) { if (S[i * 2 + n] != '?' && S[i * 2 + n] != get<0>(bnormal[m])[n]) flag = false; }
						if (flag == true) {
							int G1 = get<1>(bnormal[m]) + get<2>(bnormal[m]);
							int G2 = 0;
							if (get<0>(bnormal[m])[1] == '/') G2 = j; // 1 回前
							if (get<0>(bnormal[m])[0] == 'x') G2 = j + k; // 2 回前
							int v1 = get<1>(bnormal[m]), v2 = get<2>(bnormal[m]);
							if (v1 == 10) { v2 = j; }

							if (l >= G1 + G2) {
								dp[i][v1][v2][l - (G1 + G2)] += dp[i + 1][j][k][l];
							}
						}
					}
				}
			}
		}
	}
	long long sum = 0;
	for (int i = 0; i <= 10; i++) { for (int j = 0; j <= 10; j++) sum += dp[0][i][j][0]; }
	return sum;
}

int main() {
	init();
	int Q, N; string str;
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> N >> str; vector<int>A(N, 0);
		for (int j = 0; j < N; j++) cin >> A[j];
		cout << solve(str, A) << endl;
	}
	return 0;
}

Compilation message (stderr)

bow.cpp: In function 'long long int solve(std::__cxx11::string, std::vector<int>)':
bow.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < blast.size(); i++) {
                  ~~^~~~~~~~~~~~~~
bow.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int m = 0; m < bnormal.size(); m++) {
                      ~~^~~~~~~~~~~~~~~~

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