Submission #1040275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040275		shezitt	Miners (IOI07_miners)	C++14	100 / 100	672 ms	217460 KiB

miners

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

}

• 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