# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
501069 |
2022-01-02T10:22:24 Z |
600Mihnea |
Miners (IOI07_miners) |
C++17 |
|
111 ms |
101012 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 7;
const int INF = (int) 1e9;
int n;
int type[N];
int dp[N][4][4][4][4];
int memo[4][4][4];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
for (int a = 0; a < 4; a++) {
for (int b = 0; b < 4; b++) {
for (int c = 0; c < 4; c++) {
set<int> s;
s.insert(a);
s.insert(b);
s.insert(c);
memo[a][b][c] = (int) s.size() - s.count(0);
}
}
}
{
string s;
cin >> n >> s;
int Index = 0;
map<char, int> MP;
for (int i = 1; i <= n; i++) {
char ch = s[i - 1];
if (!MP.count(ch)) {
MP[ch] = ++Index;
}
type[i] = MP[ch];
}
for (int i = 1; i <= n; i++) {
assert(1 <= type[i] && type[i] <= 3);
}
}
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++) {
dp[i][a][b][c][d] = -INF;
}
}
}
}
}
dp[0][0][0][0][0] = 0;
for (int i = 0; i < n; i++) {
int x = type[i + 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++) {
dp[i + 1][a][b][d][x] = max(dp[i + 1][a][b][d][x], dp[i][a][b][c][d] + memo[c][d][x]);
dp[i + 1][b][x][c][d] = max(dp[i + 1][b][x][c][d], dp[i][a][b][c][d] + memo[a][b][x]);
}
}
}
}
}
int sol = -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++) {
sol = max(sol, dp[n][a][b][c][d]);
}
}
}
}
cout << sol << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
100416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
100444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
100432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
100388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
100448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
100456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
100424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
100524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
100516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
100552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
100920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
101012 KB |
Output is correct |