# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
54539 | 2018-07-04T04:01:43 Z | 강태규(#1489) | Miners (IOI07_miners) | C++11 | 1196 ms | 952 KB |
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_map> #include <functional> #include <cstring> #include <cmath> #include <ctime> #include <cstdlib> using namespace std; typedef long long llong; typedef long double ld; typedef pair<int, int> pii; typedef pair<llong, llong> pll; const int inf = 1e8; int tr[256]; int dp1[64][64]; int dp2[64][64]; pii getCoal(int x, int p) { static int cnt[4]; cnt[1] = cnt[2] = cnt[3] = 0; int nxt = (x << 2 | p) & 63; cnt[p] = 1; cnt[x & 3] = 1; cnt[(x >> 2) & 3] = 1; return pii(nxt, cnt[1] + cnt[2] + cnt[3]); } int imax(int x, int y) { return x < y ? y : x; } int n; char str[100001]; int main() { tr['M'] = 1; tr['F'] = 2; tr['B'] = 3; scanf("%d%s", &n, str); for (int i = 0; i < 64; ++i) { for (int j = 0; j < 64; ++j) { dp1[i][j] = -inf; dp2[i][j] = -inf; } } int nxt, val; dp1[0][0] = 0; for (int it = 0; it < n; ++it) { int i = tr[str[it]]; for (int j = 0; j < 64; ++j) { for(int k = 0; k < 64; ++k) { if (dp1[j][k] < 0) continue; tie(nxt, val) = getCoal(j, i); dp2[nxt][k] = imax(dp2[nxt][k], dp1[j][k] + val); tie(nxt, val) = getCoal(k, i); dp2[j][nxt] = imax(dp2[j][nxt], dp1[j][k] + val); } } for (int j = 0; j < 64; ++j) { for (int k = 0; k < 64; ++k) { dp1[j][k] = dp2[j][k]; dp2[j][k] = -inf; } } } int ans = 0; for (int i = 0; i < 64; ++i) { for (int j = 0; j < 64; ++j) { ans = imax(ans, dp1[i][j]); } } printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 612 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 612 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 612 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 121 ms | 664 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 297 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 820 ms | 836 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1196 ms | 952 KB | Output is correct |