Submission #1011379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011379		kaopj	Miners (IOI07_miners)	C++17	68 / 100	1577 ms	322460 KiB

miners

#include <iostream>
#include <vector>
#include <map>
#define lgm cin.tie(0)->sync_with_stdio(0);
using namespace std;
signed main() {
    lgm;
    int n;
    cin >> n;
    char x[n+1];
    vector<int> c(n);
    cin >> x;
    for (int i=0;i<n;i++) {
        if (x[i] == 'M') {
            c[i]=1;
        } else if (x[i] == 'B') {
            c[i]=2;
        } else {
            c[i]=3;
        }
    }
    map<tuple<int,vector<int>,vector<int>>,long long> dp;
    auto dfs = [&] (auto dfs,int p,vector<int> a,vector<int> b)->long long {
        if (dp[{p,a,b}] != 0) {
            return dp[{p,a,b}];
        }
        vector<int> ua=a,ub=b;
        int sa=0,sb=0;
        bool hm=0,hb=0,hf=0;
        ua[0]=ua[1];
        ua[1]=ua[2];
        ua[2]=c[p];
        ub[0]=ub[1];
        ub[1]=ub[2];
        ub[2]=c[p];
        for (int i=0;i<3;i++) {
            if (ua[i] == 1) {
                sa+=1-hm;
                hm=1;
            } else if (ua[i] == 2) {
                sa+=1-hb;
                hb=1;
            } else if (ua[i] == 3) {
                sa+=1-hf;
                hf=1;
            }
        }
        hm=0; hb=0; hf=0;
        for (int i=0;i<3;i++) {
            if (ub[i] == 1) {
                sb+=1-hm;
                hm=1;
            } else if (ub[i] == 2) {
                sb+=1-hb;
                hb=1;
            } else if (ub[i] == 3) {
                sb+=1-hf;
                hf=1;
            }
        }
        if (p == n-1) {
            return dp[{p,a,b}]=max(sa,sb);
        }
        return dp[{p,a,b}]=max(sa+dfs(dfs,p+1,ua,b),sb+dfs(dfs,p+1,a,ub));
    };
    cout << dfs(dfs,0,{0,0,0},{0,0,0});
    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: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8