# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
159799 | 2019-10-24T16:41:07 Z | karma | Miners (IOI07_miners) | C++14 | 137 ms | 100852 KB |
#include<bits/stdc++.h> #define FileName "test" #define ll long long #define pb emplace_back #define fi first #define se second #define mp make_pair using namespace std; typedef pair<ll, ll> pii; const int N = int(1e5) + 5; int f[N][4][4][4][4]; int cost[4][4][4], n, c; string s; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(FileName".inp", "r")) { freopen(FileName".inp", "r", stdin); freopen(FileName".out", "w", stdout); } cin >> n >> s; for(int i = 0; i < 4; ++i) { for(int j = 0; j < 4; ++j) { for(int k = 0; k < 4; ++k) { set<int> s; s.insert(i), s.insert(j), s.insert(k), s.erase(0); cost[i][j][k] = int(s.size()); } } } s = ' ' + s; memset(&f, -1, sizeof f); f[0][0][0][0][0] = 0; for(int i = 1; i <= n; ++i) { if(s[i] == 'B') c = 1; else if(s[i] == 'M') c = 2; else if(s[i] == 'F') c = 3; for(int j = 0; j < 4; ++j) { for(int k = 0; k < 4; ++k) { for(int t = 0; t < 4; ++t) { for(int l = 0; l < 4; ++l) { if(f[i - 1][j][k][t][l] == -1) continue; f[i][j][k][l][c] = max(f[i][j][k][l][c], f[i - 1][j][k][t][l] + cost[t][l][c]); f[i][k][c][t][l] = max(f[i][k][c][t][l], f[i - 1][j][k][t][l] + cost[j][k][c]); } } } } } int res = 0; for(int i = 0; i < 4; ++i) { for(int j = 0; j < 4; ++j) { for(int k = 0; k < 4; ++k) { for(int l = 0; l < 4; ++l) res = max(res, f[n][i][j][k][l]); } } } cout << res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 85 ms | 100600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 85 ms | 100560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 88 ms | 100568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 88 ms | 100584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 85 ms | 100572 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 84 ms | 100484 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 97 ms | 100480 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 88 ms | 100592 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 90 ms | 100600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 109 ms | 100592 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 122 ms | 100824 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 137 ms | 100852 KB | Output is correct |