제출 #547802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
547802		StrawHatWess	Miners (IOI07_miners)	C++17	100 / 100	920 ms	648 KiB

miners

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

#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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][10][10];
//unordered_map<string, int> ind;
vi ind(10000); 
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) 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;
        return 2;
    }
    return 1;

}

int f(string s){
    int ans=0; 
    for(char c: s){
        ans*=27; 
        ans+=c-'A'+1; 
    }
    return ans;
}


int main() {
    IO(); boost; 

    cin >> n >> s;
    ind[f("")] = 0; 
    ind[f("MM")] = 1; ind[f("MF")] = 2; ind[f("MB")] = 3; 
    ind[f("BB")] = 4; ind[f("BM")] = 5; ind[f("BF")] = 6; 
    ind[f("FF")] = 7; ind[f("FB")] = 8; ind[f("FM")] = 9; 
    ind[f("M")] = 1; ind[f("B")] = 4; ind[f("F")] = 7;
    
    for (int i=n-1; i>=0; i--) {
        for (int j = 0; j<=9; j++) {
            for (int k=0; k<=9; k++) {
                if(!k && !j && i) break; 

                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[f(nwS1)]][k] + val(lstS1, s[i]);
                int c2 = dp[(i+1)&1][j][ind[f(nwS2)]] + val(lstS2, s[i]);
               
                dp[i&1][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