# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
366171 |
2021-02-13T12:25:45 Z |
ngpin04 |
Miners (IOI07_miners) |
C++11 |
|
122 ms |
101200 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N];
int dp[N][4][4][4][4];
void maxi(int &a, int b)
{
if (a < b)
a = b;
}
int cost(int a, int b, int c)
{
int res = 0;
if (a < 3)
res++;
if (b < 3 && a != b)
res++;
if (c < 3 && a != c && b != c)
res++;
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("file.inp","r",stdin);
cin >> n;
for (int i = 1; i <= n; i++)
{
char c;
cin >> c;
if (c == 'B')
a[i] = 0;
else if (c == 'M')
a[i] = 1;
else
a[i] = 2;
}
memset(dp, -1, sizeof(dp));
dp[1][3][3][3][3] = 0;
int ans = 0;
for (int i = 1; i <= n; i++)
for (int x = 0; x <= 3; x++)
for (int y = 0; y <= 3; y++)
for (int u = 0; u <= 3; u++)
for (int v = 0; v <= 3; v++)
{
int cur = dp[i][x][y][u][v];
if (cur < 0)
continue;
maxi(dp[i + 1][y][a[i]][u][v], cur + cost(x, y, a[i]));
maxi(dp[i + 1][x][y][v][a[i]], cur + cost(u, v, a[i]));
if (i == n)
{
maxi(ans, dp[i + 1][y][a[i]][u][v]);
maxi(ans, dp[i + 1][x][y][v][a[i]]);
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
100588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
100524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
100588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
100588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
100588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
100588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
100588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
100588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
100628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
100716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
101032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
101200 KB |
Output is correct |