# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
447994 |
2021-07-28T12:16:48 Z |
rainboy |
Miners (IOI07_miners) |
C |
|
129 ms |
580 KB |
#include <stdio.h>
#include <string.h>
#define N 100000
int max(int a, int b) { return a > b ? a : b; }
char used[4];
int count(int a, int b, int c) {
int k;
memset(used, 0, sizeof used);
k = 0;
if (a > 0 && !used[a])
used[a] = 1, k++;
if (b > 0 && !used[b])
used[b] = 1, k++;
if (c > 0 && !used[c])
used[c] = 1, k++;
return k;
}
int main() {
static char cc[N + 1];
static int dp[4][4][4][4], dq[4][4][4][4];
int n, i, a, b, c, d, ans;
scanf("%d%s", &n, cc);
memset(dp, -1, sizeof dp);
dp[0][0][0][0] = 0;
for (i = 0; i < n; i++) {
int e = cc[i] == 'M' ? 1 : (cc[i] == 'F' ? 2 : 3);
memset(dq, -1, sizeof dq);
for (a = 0; a < 4; a++)
for (b = 0; b < 4; b++)
for (c = 0; c < 4; c++)
for (d = 0; d < 4; d++) {
int x = dp[a][b][c][d];
if (x == -1)
continue;
dq[b][e][c][d] = max(dq[b][e][c][d], x + count(a, b, e));
dq[a][b][d][e] = max(dq[a][b][d][e], x + count(c, d, e));
}
for (a = 0; a < 4; a++)
for (b = 0; b < 4; b++)
for (c = 0; c < 4; c++)
for (d = 0; d < 4; d++)
dp[a][b][c][d] = dq[a][b][c][d];
}
ans = 0;
for (a = 0; a < 4; a++)
for (b = 0; b < 4; b++)
for (c = 0; c < 4; c++)
for (d = 0; d < 4; d++)
ans = max(ans, dp[a][b][c][d]);
printf("%d\n", ans);
return 0;
}
Compilation message
miners.c: In function 'main':
miners.c:29:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d%s", &n, cc);
| ^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
580 KB |
Output is correct |