oj.uz

Submission #410572

# Submission time Handle Problem Language Result Execution time Memory
410572 2021-05-23T03:03:21 Z dongliu0426 Miners (IOI07_miners) C++17
100 / 100
 211 ms 608 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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