Submission #319165

#	Time	Username	Problem	Language	Result	Execution time	Memory
319165		Temmie	Miners (IOI07_miners)	C++17	100 / 100	960 ms	100708 KiB

miners

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	//std::vector <std::vector <std::vector <std::vector <std::vector <int>>>>> dp(
	//1e5 + 3, std::vector <std::vector <std::vector <std::vector <int>>>> (4,
	//std::vector <std::vector <std::vector <int>>> (4,
	//std::vector <std::vector <int>> (4,
	//std::vector <int> (4, 0)))));
	//dp.front().front().front().front().front() = 1;
	int dp[(int)1e5 + 3][4][4][4][4];
	for (int i = 0; i < 1e5 + 3; i++) for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++) for (int l = 0; l < 4; l++)
					for (int o = 0; o < 4; o++) dp[i][j][k][l][o] = 0;
	dp[0][0][0][0][0] = 1;
	int n; std::cin >> n;
	for (int i = 0; i < n; i++) {
		char c; std::cin >> c;
		int now = (c == 'M') + 2 * (c == 'B') + 3 * (c == 'F');
		for (int j = 0; j < 4; j++) for (int k = 0; k < 4; k++)
				for (int l = 0; l < 4; l++) for (int o = 0; o < 4; o++) {
						if (!dp[i][j][k][l][o]) continue;
						std::set <int> st1, st2;
						st1.insert(j); st1.insert(k); st1.insert(now);
						st2.insert(l); st2.insert(o); st2.insert(now);
						st1.erase(0); st2.erase(0);
						dp[i + 1][k][now][l][o] = std::max(dp[i + 1][k][now][l][o], dp[i][j][k][l][o] + (int)st1.size());
						dp[i + 1][j][k][o][now] = std::max(dp[i + 1][j][k][o][now], dp[i][j][k][l][o] + (int)st2.size());
					}
	}
	int ans = 0;
	for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++) for (int l = 0; l < 4; l++)
					ans = std::max(ans, dp[n][i][j][k][l] - 1);
	std::cout << ans << "\n";
	//std::cout.flush(); std::cin >> n;
	
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8