Submission #367406

#	Time	Username	Problem	Language	Result	Execution time	Memory
367406		NachoLibre	Miners (IOI07_miners)	C++17	100 / 100	150 ms	100972 KiB

miners

#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 / 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