Submission #537364

#	Time	Username	Problem	Language	Result	Execution time	Memory
537364		andecaandeci	Miners (IOI07_miners)	C++17	100 / 100	1148 ms	146704 KiB

miners

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int dp[N][4][4][4][4];
map<char, int>m;

int n;
string s;

void init(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 4; j++){
            for(int k = 0; k < 4; k++){
                for(int l = 0; l < 4; l++){
                    for(int m = 0; m < 4; m++)
                        dp[i][j][k][l][m] = -1;
                }
            }
        }
    }
}

int f(int idx, int la2, int la1, int lb2, int lb1){
    if(idx == n) return 0;

    int &cur = dp[idx][la2][la1][lb2][lb1];

    if(cur != -1) return cur;

    set<int>s1, s2;
    
    if(la2 > 0) s1.insert(la2);
    if(la1 > 0) s1.insert(la1);
    if(lb2 > 0) s2.insert(lb2);
    if(lb1 > 0) s2.insert(lb1);

    s1.insert(m[s[idx]]);
    s2.insert(m[s[idx]]);

    int score1, score2;
    score1 = s1.size(); score2 = s2.size();

    cur = max(
        f(idx + 1, la1, m[s[idx]], lb2, lb1) + score1,
        f(idx + 1, la2, la1, lb1, m[s[idx]]) + score2
    );

    return cur;
}

int main(){
    init();
    cin >> n;
    cin >> s;

    m['M'] = 1;
    m['B'] = 2;
    m['F'] = 3;

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

    return 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