Submission #1218962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218962		somefolk	Miners (IOI07_miners)	C++20	100 / 100	668 ms	980 KiB

miners

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <complex>
#include <list>
#include <cassert>
#include <chrono>
#include <random>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define endl "\n"
// #define int long long

const int INF = 1e9+7;
const int MOD = 1e9+7;

int check(int a, int b, int c){
    unordered_set<int> st;
    if(a) st.insert(a);
    if(b) st.insert(b);
    if(c) st.insert(c);
    return (int)st.size();
}

void solve(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        if(s[i] == 'M') a[i] = 1;
        if(s[i] == 'F') a[i] = 2;
        if(s[i] == 'B') a[i] = 3;
    }

    vector<vector<vector<vector<int>>>> dp1(4, vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1))));
    vector<vector<vector<vector<int>>>> dp2(4, vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1))));
    dp1[0][0][0][0] = 0;

    for(int i = 0; i < n; i++){
        for(int a1=0; a1<4; a1++) for(int b1=0; b1<4; b1++) for(int a2=0; a2<4; a2++) for(int b2=0; b2<4; b2++){
            dp2[a1][b1][a2][b2] = -1;
        }

        for(int a1 = 0; a1 < 4; a1++){
            for(int b1 = 0; b1 < 4; b1++){
                for(int a2 = 0; a2 < 4; a2++){
                    for(int b2 = 0; b2 < 4; b2++){
                        if(dp1[a1][b1][a2][b2] == -1) continue;

                        int cnt1 = check(a1, b1, a[i]);
                        dp2[b1][a[i]][a2][b2] = max(dp2[b1][a[i]][a2][b2], dp1[a1][b1][a2][b2]+cnt1);

                        int cnt2 = check(a2, b2, a[i]);
                        dp2[a1][b1][b2][a[i]] = max(dp2[a1][b1][b2][a[i]], dp1[a1][b1][a2][b2]+cnt2);
                    }
                }
            }
        }

        dp1 = dp2;
    }

    int sol = 0;
    for(int a1 = 0; a1 < 4; a1++){
        for(int b1 = 0; b1 < 4; b1++){
            for(int a2 = 0; a2 < 4; a2++){
                for(int b2 = 0; b2 < 4; b2++){
                    sol = max(sol, dp1[a1][b1][a2][b2]);
                }
            }
        }
    }

    cout << sol << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    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