# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
248718 |
2020-07-13T08:55:09 Z |
WLZ |
Miners (IOI07_miners) |
C++14 |
|
1143 ms |
101088 KB |
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
map<char, int> mp = {{'M', 1}, {'B', 2}, {'F', 3}};
int dp[n + 1][4][4][4][4];
memset(dp, -1, sizeof dp);
auto f = [](int a, int b, int c) {
set<int> st;
if (a != 0) {
st.insert(a);
}
if (b != 0) {
st.insert(b);
}
if (c != 0) {
st.insert(c);
}
return (int) st.size();
};
dp[0][0][0][0][0] = 0;
for (int i = 1; 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++) {
if (dp[i - 1][a][b][c][d] == -1) {
continue;
}
dp[i][b][mp[s[i - 1]]][c][d] = max(dp[i][b][mp[s[i - 1]]][c][d], dp[i - 1][a][b][c][d] + f(a, b, mp[s[i - 1]]));
dp[i][a][b][d][mp[s[i - 1]]] = max(dp[i][a][b][d][mp[s[i - 1]]], dp[i - 1][a][b][c][d] + f(c, d, mp[s[i - 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++) {
ans = max(ans, dp[n][a][b][c][d]);
}
}
}
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
120 ms |
10432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
25524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
525 ms |
75788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1143 ms |
101088 KB |
Output is correct |