Submission #970475

#	Time	Username	Problem	Language	Result	Execution time	Memory
970475		jadai007	Miners (IOI07_miners)	C++14	100 / 100	144 ms	1140 KiB

miners

#include<bits/stdc++.h>

using namespace std;

int dp[2][4][4][4][4],n,arr[100001],ans = -1;
string s;

int cal(int i,int j,int k){
    int t=0;
    if(i==1||j==1||k==1)t++;
    if(i==2||j==2||k==2)t++;
    if(i==3||j==3||k==3)t++;
    return t;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>n>>s;
    for(int i = 1; i<=n; ++i){
        if(s[i-1]=='M') arr[i] = 1;
        else if(s[i-1]=='B') arr[i] = 2;
        else if(s[i-1]=='F') arr[i] = 3;
    }
    dp[0][arr[1]][0][0][0] = dp[0][0][0][arr[1]][0] = 1;
    for(int idx = 2; idx<=n; ++idx){
        int x = arr[idx];
        for(int i = 0; i<=3; ++i){
            for(int j = 0; j<=3; ++j){
                for(int k = 0; k<=3; ++k){
                    for(int l = 0; l<=3; ++l){
                        if(!dp[0][i][j][k][l]) continue;
                        dp[1][x][i][k][l] = max(dp[1][x][i][k][l], dp[0][i][j][k][l] + cal(x,i,j));
                        dp[1][i][j][x][k] = max(dp[1][i][j][x][k], dp[0][i][j][k][l] + cal(x,k,l));
                    }
                }
            }
        }
        for(int i = 0; i<=3; ++i){
            for(int j = 0; j<=3; ++j){
                for(int k = 0; k<=3; ++k){
                    for(int l = 0; l<=3; ++l){
                        dp[0][i][j][k][l] = dp[1][i][j][k][l];
                    }
                }
            }
        }
    }
    for(int i = 0; i<=3; ++i){
        for(int j = 0; j<=3; ++j){
            for(int k = 0; k<=3; ++k){
                for(int l = 0; l<=3; ++l){
                    ans = max(ans,  dp[1][i][j][k][l]);
                }
            }
        }
    }
    cout<<ans;
}

• 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