oj.uz

Submission #707783

# Submission time Handle Problem Language Result Execution time Memory
707783 2023-03-10T06:26:33 Z TAhmed33 Miners (IOI07_miners) C++
100 / 100
 179 ms 1104 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> adds;
int main () {
	string s;
	cin >> n >> s;
	for (auto i : s) {
		if (i == 'M') adds.push_back(1);
		else if (i == 'F') adds.push_back(2);
		else adds.push_back(3);
	}
	int dp[4][4][4][4][2] = {};
	for (int i = n - 1; i >= 0; i--) {
		for (int a = 0; a <= 3; a++) {
			for (int b = 0; b <= 3; b++) {
				for (int c = 0; c <= 3; c++) {
					for (int d = 0; d <= 3; d++) {
						int cnt = 0;
						if (a == 0 && b == 0) {
							cnt = 1;
						} else if (a && !b) {
							cnt = 1 + (a != adds[i]);
						} else if (b && !a) {
							cnt = 1 + (b != adds[i]);
						} else {
							if (a == b && a == adds[i]) {
								cnt = 1;
							} else if (a == b && a != adds[i]) {
								cnt = 2;
							} else if (b == adds[i] && a != b) {
								cnt = 2;
							} else if (a == adds[i] && a != b) {
								cnt = 2;
							} else {
								cnt = 3;
							}
						}
						int x = dp[b][adds[i]][c][d][1] + cnt;
						if (c == 0 && d == 0) {
							cnt = 1;
						} else if (c && !d) {
							cnt = 1 + (c != adds[i]);
						} else if (d && !c) {
							cnt = 1 + (d != adds[i]);
						} else {
							if (c == d && c == adds[i]) {
								cnt = 1;
							} else if (c == d && c != adds[i]) {
								cnt = 2;
							} else if (d == adds[i] && c != d) {
								cnt = 2;
							} else if (c == adds[i] && c != d) {
								cnt = 2;
							} else {
								cnt = 3;
							}
						}
						dp[a][b][c][d][0] = max(x, dp[a][b][d][adds[i]][1] + cnt);
					}
				}
			}
		}
		for (int a = 0; a <= 3; a++) {
			for (int b = 0; b <= 3; b++) {
				for (int c = 0; c <= 3; c++) {
					for (int d = 0; d <= 3; d++) {
						dp[a][b][c][d][1] = dp[a][b][c][d][0];
					}
				}
			}
		}
	}
	cout << dp[0][0][0][0][1] << '\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 412 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 468 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 976 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 1104 KB Output is correct