# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
54603 | 2018-07-04T07:51:42 Z | imeimi2000 | Miners (IOI07_miners) | C++17 | 87 ms | 704 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[16][16]; int dp2[16][16]; int nxt[16][4]; int cnt[16][4]; pii getCoal(int x, int p) { static int cnt[4]; cnt[1] = cnt[2] = cnt[3] = 0; int nxt = (x << 2 | p) & 15; cnt[p] = 1; cnt[x & 3] = 1; cnt[x >> 2] = 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; for (int i = 0; i < 16; ++i) { for (int j = 1; j <= 3; ++j) { tie(nxt[i][j], cnt[i][j]) = getCoal(i, j); } } scanf("%d%s", &n, str); for (int i = 0; i < 16; ++i) { for (int j = 0; j < 16; ++j) { dp1[i][j] = -inf; dp2[i][j] = -inf; } } dp1[0][0] = 0; for (int it = 0; it < n; ++it) { int i = tr[str[it]]; for (int j = 0; j < 16; ++j) { for(int k = 0; k < 16; ++k) { if (dp1[j][k] < 0) continue; dp2[nxt[j][i]][k] = imax(dp2[nxt[j][i]][k], dp1[j][k] + cnt[j][i]); dp2[j][nxt[k][i]] = imax(dp2[j][nxt[k][i]], dp1[j][k] + cnt[k][i]); } } for (int j = 0; j < 16; ++j) { for (int k = 0; k < 16; ++k) { dp1[j][k] = dp2[j][k]; dp2[j][k] = -inf; } } } int ans = 0; for (int i = 0; i < 16; ++i) { for (int j = 0; j < 16; ++j) { ans = imax(ans, dp1[i][j]); } } printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 252 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 356 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 508 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 544 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 544 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 544 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 592 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 620 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 620 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 680 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 704 KB | Output is correct |