Submission #410572

#	Time	Username	Problem	Language	Result	Execution time	Memory
410572		dongliu0426	Miners (IOI07_miners)	C++17	100 / 100	211 ms	608 KiB

miners

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define f first
#define s second

const int N = 100000;

int dp[2][4][4][4][4];

int unique(int a, int b, int c) {
	if (a == 0 && b == 0)
		return 1;
	if (a == 0 || a == b)
		return 1 + (b != c);
	return 2 + (a != c && b != c);
}

bool ckmax(int& a, const int& b) {
	return (a < b ? a = b, true : false);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);

	int n; string s;
	cin >> n >> s;
	memset(dp[0], -0x3f, sizeof(dp[0]));
	dp[0][0][0][0][0] = 0;
	for (char ch : s) {
		int i = ch == 'M' ? 1 : (ch == 'F' ? 2 : 3);
		memset(dp[1], -0x3f, sizeof(dp[1]));
		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) {
						ckmax(dp[1][b][i][c][d], dp[0][a][b][c][d] + unique(a, b, i));
						ckmax(dp[1][a][b][d][i], dp[0][a][b][c][d] + unique(c, d, i));
					}
		swap(dp[0], dp[1]);
	}
	int ans = 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)
					ckmax(ans, dp[0][a][b][c][d]);
	cout << ans << '\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