oj.uz

Submission #367406

# Submission time Handle Problem Language Result Execution time Memory
367406 2021-02-17T07:55:22 Z NachoLibre Miners (IOI07_miners) C++17
100 / 100
 150 ms 100972 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, x[N][4][4][4][4];
string s;

inline int X(int a, int b, int c) {
	if(a > b) swap(a, b);
	if(b > c) swap(b, c);
	if(a > b) swap(a, b);
	if(a + b + c == 0) return 0;
	if(a + b == 0) return 1;
	if(a == 0) return 1 + (b != c);
	return 1 + (a != b) + (b != c);
}

inline void Y(int &a, int b) {
	a = max(a, b);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	for(int i = 0; i <= n; ++i) {
		for(int a = 0; a < 4; ++a) {
			for(int b = 0; b < 4; ++b) {
				for(int c = 0; c < 4; ++c) {
					for(int d = 0; d < 4; ++d) {
						x[i][a][b][c][d] = -1;
					}
				}
			}
		}
	}
	x[0][0][0][0][0] = 0;
	for(int i = 1; i <= n; ++i) {
		int y = (s[i - 1] == 'F' ? 1 : (s[i - 1] == 'M' ? 2 : 3));
		for(int a = 0; a < 4; ++a) {
			for(int b = 0; b < 4; ++b) {
				for(int c = 0; c < 4; ++c) {
					for(int d = 0; d < 4; ++d) {
						if(x[i - 1][a][b][c][d] == -1) continue;
						Y(x[i][b][y][c][d], x[i - 1][a][b][c][d] + X(a, b, y));
						Y(x[i][a][b][d][y], x[i - 1][a][b][c][d] + X(c, d, y));
					}
				}
			}
		}
	}
	int fp = 0;
	for(int a = 0; a < 4; ++a) {
		for(int b = 0; b < 4; ++b) {
			for(int c = 0; c < 4; ++c) {
				for(int d = 0; d < 4; ++d) {
					Y(fp, x[n][a][b][c][d]);
				}
			}
		}
	}
	cout << fp << endl;
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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