제출 #964856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964856		anango	Miners (IOI07_miners)	C++17	100 / 100	215 ms	205188 KiB

miners

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

int has(int a, int b, int c, int d) {
    return 64*a+16*b+4*c+d;
}
int dis(int a, int b, int c) {
    if (a==0) {
        if (b==0) {
            if (c==0) {
                return 0;
            }
            return 1;
        }
        return 1+(b!=c);
    }
    if (b==0) {
        if (a==0) {
            if (c==0) {
                return 0;
            }
            return 1;
        }
        return 1+(a!=c);
    }
    if (c==0) {
        if (b==0) {
            if (a==0) {
                return 0;
            }
            return 1;
        }
        return 1+(a!=b);
    }
    if (a==b && b==c) {
        return 1;
    }
    if (a==b || a==c || b==c) {
        return 2;
    }
    return 3;
}
signed main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int INF=1000000007;
    vector<vector<int>> dp(n+1,vector<int>(256,-INF));
    dp[0][has(0,0,0,0)] = 0;
    //store the last two shipments to mine 1 and the last two shipments to mine 2
    for (int ind=1; ind<=n; ind++) {
        int cursh = s[ind-1];
        int t=-10;
        if (cursh=='M') {
            t=1;
        }
        else if (cursh=='F') {
            t=2;
        }  
        else {
            t=3;
        }
        for (int psh1=0; psh1<4; psh1++) {
            for (int psh2=0; psh2<4; psh2++) {
                for (int psh3=0; psh3<4; psh3++) {
                    for (int psh4=0; psh4<4; psh4++) {
                        int H=dp[ind-1][has(psh1,psh2,psh3,psh4)];
                        dp[ind][has(psh2,t,psh3,psh4)] = max(dp[ind][has(psh2,t,psh3,psh4)],H+dis(psh1,psh2,t));
                        dp[ind][has(psh1,psh2,psh4,t)] = max(dp[ind][has(psh1,psh2,psh4,t)],H+dis(psh3,psh4,t));
                    }
                }
            }
        }
    }
    int ma=-1;
    for (int psh1=0; psh1<4; psh1++) {
        for (int psh2=0; psh2<4; psh2++) {
            for (int psh3=0; psh3<4; psh3++) {
                for (int psh4=0; psh4<4; psh4++) {
                   ma=max(ma,dp[n][has(psh1,psh2,psh3,psh4)]);
                }
            }
        }
    }
    cout << ma << 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