제출 #397238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397238		AugustinasJucas	Miners (IOI07_miners)	C++14	100 / 100	1006 ms	100696 KiB

miners

#include <bits/stdc++.h>

using namespace std;
int n;
string a;
int hsh(char a){
    if(a == 'M') return 1;
    if(a == 'B') return 2;
    if(a == 'F') return 3;
    return 0;
}
const int dydis = 1e5+10;
const int inf = 1e9;
int dp[dydis][4][4][4][4];
int kek(int a, int b, int c){
    set<int> st = {a, b, c};
    return st.size() - st.count(0);
}
int main(){
    for(int i = 0; i < dydis; i++){
        for(int j = 0; j < 4; j++){
            for(int h = 0; h < 4; h++){
                for(int l = 0; l < 4; l++){
                    for(int g = 0; g < 4; g++){
                        dp[i][j][h][l][g] = -inf;
                    }
                }
            }
        }
    }
    cin >> n >> a;
    dp[0][0][0][0][0] = 0;

    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            for(int h = 0; h < 4; h++){
                for(int l = 0; l < 4; l++){
                    for(int g = 0; g < 4; g++){
                        if(dp[i][j][h][l][g] < 0) continue;
                        dp[i+1][h][hsh(a[i])][l][g] = max(dp[i+1][h][hsh(a[i])][l][g], dp[i][j][h][l][g] + kek(j, h, hsh(a[i])));
                        dp[i+1][j][h][g][hsh(a[i])] = max(dp[i+1][j][h][g][hsh(a[i])], dp[i][j][h][l][g] + kek(l, g, hsh(a[i])));
                        ans = max(ans, dp[i+1][h][hsh(a[i])][l][g]);
                        ans = max(ans, dp[i+1][j][h][g][hsh(a[i])]);                    }
                }
            }
        }
    }
    cout << ans;
    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