Submission #122235

#	Time	Username	Problem	Language	Result	Execution time	Memory
122235		Osama_Alkhodairy	Miners (IOI07_miners)	C++17	100 / 100	1256 ms	108732 KiB

miners

#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8