Submission #547799

#	Time	Username	Problem	Language	Result	Execution time	Memory
547799		StrawHatWess	Miners (IOI07_miners)	C++17	100 / 100	1294 ms	504 KiB

miners

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define F first
#define S second
#define PB push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
const int maxn = 1e5 + 5;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)

#define dbg(x) cerr << #x << " : " << x << endl; 

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}

//---------------------------------------------

int n, dp[2][14][14];
unordered_map<string, int> ind;
vector<string> ind2 = {"", "MM", "MF", "MB", "BB", "BM", "BF", "FF", "FB", "FM", "M", "B", "F"};
string s;

int val(string x, char c) {
    if (x.size() == 2) {
        char a = x[0], b = x[1];
        if (a==b && b == c && c == a) return 1;
        if (a != b && b != c && c != a) return 3;
        return 2;
    }
    if (x.size() == 1) {
        char a = x[0];
        if (a == c) return 1;
        else return 2;
    }
    return 1;

}


int main() {
    IO(); 

    cin >> n >> s;
    ind[""] = 0; 
    ind["MM"] = 1; ind["MF"] = 2; ind["MB"] = 3; 
    ind["BB"] = 4; ind["BM"] = 5; ind["BF"] = 6; 
    ind["FF"] = 7; ind["FB"] = 8; ind["FM"] = 9; 
    ind["M"] = 1; ind["B"] = 4; ind["F"] = 7;
    
    for (int i=n-1; i>=0; i--) {
        for (int j = 0; j <= 9; j++) {
            for (int k=0; k <=9; k++) {
                string lstS1, lstS2, nwS1, nwS2;
                lstS1 = ind2[j], lstS2 = ind2[k];
                
                
                if(sz(lstS1)) nwS1 += lstS1.back();
                nwS1 += s[i]; 
                if(sz(lstS2)) nwS2 += lstS2.back(); 
                nwS2 += s[i];
                
                int c1 = dp[(i+1)&1][ind[nwS1]][k] + val(lstS1, s[i]);
                int c2 = dp[(i+1)&1][j][ind[nwS2]] + val(lstS2, s[i]);
               
                dp[i%2][j][k] = max(c1, c2);
            }
        }

    }
    
    cout << dp[0][0][0] << endl;
}

• 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