Submission #1011340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011340		kaopj	Miners (IOI07_miners)	C++17	68 / 100	1567 ms	344976 KiB

miners

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