# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
305503 |
2020-09-23T11:23:33 Z |
Akashi |
Miners (IOI07_miners) |
C++14 |
|
328 ms |
508 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int DIM = 1e5 + 5;
int n;
int dp[2][4][4][4][4];
char s[DIM];
int trans(char ch) {
if (ch == 'M') return 3;
if (ch == 'F') return 1;
return 2;
}
void calc(int &dp, int &aux, int a, int b, int c) {
if (a > b) swap(a, b);
if (a > c) swap(a, c);
if (b > c) swap(b, c);
if (a == b) a = 0;
if (b == c) b = 0;
int ad = (a != 0) + (b != 0) + (c != 0);
dp = max(dp, aux + ad);
}
int main() {
#ifdef HOME
freopen("miners.in", "r", stdin);
freopen("miners.out", "w", stdout);
#endif // HOME
scanf("%d", &n);
scanf("%s", s);
memset(dp, -0x3f, sizeof(dp));
dp[0][0][0][0][0] = 0;
for (int i = 1, l = 1; i <= n ; ++i, l = 1 - l) {
int tip = trans(s[i - 1]);
for (int a = 0; a <= 3 ; ++a) for(int b = 0; b <= 3 ; ++b) for (int x = 0; x <= 3 ; ++x) for (int y = 0; y <= 3 ; ++y)
dp[l][a][b][x][y] = -INF;
for (int a = 0; a <= 3 ; ++a) for(int b = 0; b <= 3 ; ++b) for (int x = 0; x <= 3 ; ++x) for (int y = 0; y <= 3 ; ++y) {
calc(dp[l][b][tip][x][y], dp[1 - l][a][b][x][y], a, b, tip);
calc(dp[l][a][b][y][tip], dp[1 - l][a][b][x][y], x, y, tip);
}
}
int ans = 0;
for (int a = 0; a <= 3 ; ++a) for(int b = 0; b <= 3 ; ++b) for (int x = 0; x <= 3 ; ++x) for (int y = 0; y <= 3 ; ++y)
ans = max(ans, dp[n % 2][a][b][x][y]);
printf("%d", ans);
return 0;
}
Compilation message
miners.cpp: In function 'int main()':
miners.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
36 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
miners.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
37 | scanf("%s", s);
| ~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
259 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
328 ms |
508 KB |
Output is correct |