Submission #122235

# Submission time Handle Problem Language Result Execution time Memory
122235 2019-06-27T22:34:57 Z Osama_Alkhodairy Miners (IOI07_miners) C++17
100 / 100
1256 ms 108732 KB
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 100001;

int n, dp[N][4][4][4][4];
string s;

int id(char c){
    if(c == 'M') return 0;
    if(c == 'B') return 1;
    if(c == 'F') return 2;
    assert(false);
}
int diff(int x, int y, int z){
    set <int> ret = {x, y, z};
    while(*ret.rbegin() == 3){
        ret.erase(--ret.end());
    }
    return ret.size();
}
int solve(int ind, int p11, int p12, int p21, int p22){
    if(ind == n) return 0;
    int &ret = dp[ind][p11][p12][p21][p22];
    if(ret != -1) return ret;
    int one = diff(id(s[ind]), p11, p12) + solve(ind + 1, id(s[ind]), p11, p21, p22);
    int two = diff(id(s[ind]), p21, p22) + solve(ind + 1, p11, p12, id(s[ind]), p21);
    return ret = max(one, two);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> s;
    cout << solve(0, 3, 3, 3, 3) << endl;
}
# Verdict Execution time Memory Grader output
1 Correct 79 ms 100600 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 80 ms 100600 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 78 ms 100600 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 81 ms 100600 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 75 ms 100516 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 76 ms 100456 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 88 ms 100640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 99 ms 100956 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 191 ms 101376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 335 ms 102520 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 597 ms 106700 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1256 ms 108732 KB Output is correct