# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
432049 | 2021-06-17T19:29:36 Z | MilosMilutinovic | Miners (IOI07_miners) | C++14 | 1500 ms | 716 KB |
#include <bits/stdc++.h> using namespace std; int dp[2][4][4][4][4]; int count_diff(int x, int y, int z) { set<int> values; if (x != 0) values.insert(x); if (y != 0) values.insert(y); if (z != 0) values.insert(z); return values.size(); } const int inf = 1e9; void clear_dp(int par) { for (int d1 = 0; d1 < 4; d1++) for (int d2 = 0; d2 < 4; d2++) for (int d3 = 0; d3 < 4; d3++) for (int d4 = 0; d4 < 4; d4++) dp[par][d1][d2][d3][d4] = -inf; } int main() { int N; scanf("%d", &N); char S[N]; scanf("%s", &S); vector<int> A(N); for (int i = 0; i < N; i++) { if (S[i] == 'M') A[i] = 1; if (S[i] == 'F') A[i] = 2; if (S[i] == 'B') A[i] = 3; } int val = A[0]; clear_dp(0); dp[0][A[0]][A[0]][0][0] = 1; dp[0][0][0][A[0]][A[0]] = 1; int curr = 1, prev = 0; for (int i = 1; i < N; i++) { int d = A[i]; clear_dp(curr); for (int d1 = 0; d1 < 4; d1++) for (int d2 = 0; d2 < 4; d2++) for (int d3 = 0; d3 < 4; d3++) for (int d4 = 0; d4 < 4; d4++) { dp[curr][d][d1][d3][d4] = max(dp[curr][d][d1][d3][d4], dp[prev][d1][d2][d3][d4] + count_diff(d, d1, d2)); dp[curr][d1][d2][d][d3] = max(dp[curr][d1][d2][d][d3], dp[prev][d1][d2][d3][d4] + count_diff(d, d3, d4)); } swap(curr, prev); } int answer = 0; for (int d1 = 1; d1 < 4; d1++) for (int d2 = 1; d2 < 4; d2++) for (int d3 = 1; d3 < 4; d3++) for (int d4 = 1; d4 < 4; d4++) answer = max(answer, dp[(N - 1) & 1][d1][d2][d3][d4]); printf("%d", answer); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 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 | 1 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 | 1 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 | 38 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 185 ms | 300 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 384 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 941 ms | 392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1569 ms | 588 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1586 ms | 716 KB | Time limit exceeded |