oj.uz

Submission #319165

# Submission time Handle Problem Language Result Execution time Memory
319165 2020-11-04T11:00:47 Z Temmie Miners (IOI07_miners) C++17
100 / 100
 960 ms 100708 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 100580 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 100452 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 100580 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 100580 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 100468 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 100540 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 100580 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 100580 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 100620 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 100708 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 100580 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 100696 KB Output is correct