Submission #1040275

#TimeUsernameProblemLanguageResultExecution timeMemory
1040275shezittMiners (IOI07_miners)C++14
100 / 100
672 ms217460 KiB
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F first
#define S second
#define ii pair<int,int>
#define dbg(x) cerr << #x << ": " << x << endl
#define raya cerr << "=============" << endl

const int N = 1e5+5;

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

map<char,int> mp = {{'M', 1}, {'F', 2}, {'B', 3}};

int calc(vi x){
    set<int> st;
    for(int val : x){
        st.insert(val);
    }
    return sz(st);
}

int f(int pos, int p1, int p2, int q1, int q2){
    if(pos == n){
        return 0;
    }
    int &res = dp[pos][p1][p2][q1][q2];
    if(res > -1){
        return res;
    }

    res = 0;

    // mina1

    if(p2 == 0){
        // no hay nada
        int profit = 1;
        res = max(res, profit + f(pos+1, p1, a[pos], q1, q2));
    }
    else if(p1 == 0){
        // hay solo uno
        int profit = calc({p2, a[pos]});
        res = max(res, profit + f(pos+1, p2, a[pos], q1, q2));
    }
    else {
        // ya hay al menos dos
        int profit = calc({p1, p2, a[pos]});
        res = max(res, profit + f(pos+1, p2, a[pos], q1, q2));
    }


    // mina2

    if(q2 == 0){
        // no hay nada
        int profit = 1;
        res = max(res, profit + f(pos+1, p1, p2, q1, a[pos]));
    }
    else if(q1 == 0){
        // hay solo uno
        int profit = calc({q2, a[pos]});
        res = max(res, profit + f(pos+1, p1, p2, q2, a[pos]));
    }
    else {
        // ya hay al menos dos
        int profit = calc({q1, q2, a[pos]});
        res = max(res, profit + f(pos+1, p1, p2, q2, a[pos]));
    }

    return res;

}

signed main(){
    memset(dp, -1, sizeof dp);
    cin >> n;
    cin >> s;
    fore(i, 0, n){
        a[i] = mp[s[i]];
    }

    cout << f(0, 0, 0, 0, 0);
    
    

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...