제출 #1357937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357937		eweirdf274r	Miners (IOI07_miners)	C++20	100 / 100	10 ms	632 KiB

miners

#include<iostream>
#include<vector>
using namespace std;
int dp[4][4][4][4][2];
int main(){
    cin.tie(NULL)->sync_with_stdio(false);
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                for(int l=0;l<4;l++)
                    for(int m=0;m<2;m++)
                        dp[i][j][k][l][m]=-1e9;
    dp[0][0][0][0][0]=0;
    for(int i=1;i<=n;i++){
        int x = i%2;
        char c=s[i-1];
        if(c=='M'){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){
                    dp[0][1][j][k][x] = max(dp[0][1][j][k][x],dp[0][0][j][k][1-x]+1);

                    dp[1][1][j][k][x] = max(dp[1][1][j][k][x],dp[0][1][j][k][1-x]+1);
                    dp[1][1][j][k][x] = max(dp[1][1][j][k][x],dp[1][1][j][k][1-x]+1);
                    dp[1][1][j][k][x] = max(dp[1][1][j][k][x],dp[2][1][j][k][1-x]+2);
                    dp[1][1][j][k][x] = max(dp[1][1][j][k][x],dp[3][1][j][k][1-x]+2);

                    dp[2][1][j][k][x] = max(dp[2][1][j][k][x],dp[0][2][j][k][1-x]+2);
                    dp[2][1][j][k][x] = max(dp[2][1][j][k][x],dp[1][2][j][k][1-x]+2);
                    dp[2][1][j][k][x] = max(dp[2][1][j][k][x],dp[2][2][j][k][1-x]+2);
                    dp[2][1][j][k][x] = max(dp[2][1][j][k][x],dp[3][2][j][k][1-x]+3);

                    dp[3][1][j][k][x] = max(dp[3][1][j][k][x],dp[0][3][j][k][1-x]+2);
                    dp[3][1][j][k][x] = max(dp[3][1][j][k][x],dp[1][3][j][k][1-x]+2);
                    dp[3][1][j][k][x] = max(dp[3][1][j][k][x],dp[2][3][j][k][1-x]+3);
                    dp[3][1][j][k][x] = max(dp[3][1][j][k][x],dp[3][3][j][k][1-x]+2);

                    dp[j][k][0][1][x] = max(dp[j][k][0][1][x],dp[j][k][0][0][1-x]+1);

                    dp[j][k][1][1][x] = max(dp[j][k][1][1][x],dp[j][k][0][1][1-x]+1);
                    dp[j][k][1][1][x] = max(dp[j][k][1][1][x],dp[j][k][1][1][1-x]+1);
                    dp[j][k][1][1][x] = max(dp[j][k][1][1][x],dp[j][k][2][1][1-x]+2);
                    dp[j][k][1][1][x] = max(dp[j][k][1][1][x],dp[j][k][3][1][1-x]+2);

                    dp[j][k][2][1][x] = max(dp[j][k][2][1][x],dp[j][k][0][2][1-x]+2);
                    dp[j][k][2][1][x] = max(dp[j][k][2][1][x],dp[j][k][1][2][1-x]+2);
                    dp[j][k][2][1][x] = max(dp[j][k][2][1][x],dp[j][k][2][2][1-x]+2);
                    dp[j][k][2][1][x] = max(dp[j][k][2][1][x],dp[j][k][3][2][1-x]+3);

                    dp[j][k][3][1][x] = max(dp[j][k][3][1][x],dp[j][k][0][3][1-x]+2);
                    dp[j][k][3][1][x] = max(dp[j][k][3][1][x],dp[j][k][1][3][1-x]+2);
                    dp[j][k][3][1][x] = max(dp[j][k][3][1][x],dp[j][k][2][3][1-x]+3);
                    dp[j][k][3][1][x] = max(dp[j][k][3][1][x],dp[j][k][3][3][1-x]+2);
                }
            }
        }
        else if(c=='B'){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){
                    dp[0][2][j][k][x] = max(dp[0][2][j][k][x],dp[0][0][j][k][1-x]+1);

                    dp[1][2][j][k][x] = max(dp[1][2][j][k][x],dp[0][1][j][k][1-x]+2);
                    dp[1][2][j][k][x] = max(dp[1][2][j][k][x],dp[1][1][j][k][1-x]+2);
                    dp[1][2][j][k][x] = max(dp[1][2][j][k][x],dp[2][1][j][k][1-x]+2);
                    dp[1][2][j][k][x] = max(dp[1][2][j][k][x],dp[3][1][j][k][1-x]+3);

                    dp[2][2][j][k][x] = max(dp[2][2][j][k][x],dp[0][2][j][k][1-x]+1);
                    dp[2][2][j][k][x] = max(dp[2][2][j][k][x],dp[1][2][j][k][1-x]+2);
                    dp[2][2][j][k][x] = max(dp[2][2][j][k][x],dp[2][2][j][k][1-x]+1);
                    dp[2][2][j][k][x] = max(dp[2][2][j][k][x],dp[3][2][j][k][1-x]+2);

                    dp[3][2][j][k][x] = max(dp[3][2][j][k][x],dp[0][3][j][k][1-x]+2);
                    dp[3][2][j][k][x] = max(dp[3][2][j][k][x],dp[1][3][j][k][1-x]+3);
                    dp[3][2][j][k][x] = max(dp[3][2][j][k][x],dp[2][3][j][k][1-x]+2);
                    dp[3][2][j][k][x] = max(dp[3][2][j][k][x],dp[3][3][j][k][1-x]+2);

                    dp[j][k][0][2][x] = max(dp[j][k][0][2][x],dp[j][k][0][0][1-x]+1);

                    dp[j][k][1][2][x] = max(dp[j][k][1][2][x],dp[j][k][0][1][1-x]+2);
                    dp[j][k][1][2][x] = max(dp[j][k][1][2][x],dp[j][k][1][1][1-x]+2);
                    dp[j][k][1][2][x] = max(dp[j][k][1][2][x],dp[j][k][2][1][1-x]+2);
                    dp[j][k][1][2][x] = max(dp[j][k][1][2][x],dp[j][k][3][1][1-x]+3);

                    dp[j][k][2][2][x] = max(dp[j][k][2][2][x],dp[j][k][0][2][1-x]+1);
                    dp[j][k][2][2][x] = max(dp[j][k][2][2][x],dp[j][k][1][2][1-x]+2);
                    dp[j][k][2][2][x] = max(dp[j][k][2][2][x],dp[j][k][2][2][1-x]+1);
                    dp[j][k][2][2][x] = max(dp[j][k][2][2][x],dp[j][k][3][2][1-x]+2);

                    dp[j][k][3][2][x] = max(dp[j][k][3][2][x],dp[j][k][0][3][1-x]+2);
                    dp[j][k][3][2][x] = max(dp[j][k][3][2][x],dp[j][k][1][3][1-x]+3);
                    dp[j][k][3][2][x] = max(dp[j][k][3][2][x],dp[j][k][2][3][1-x]+2);
                    dp[j][k][3][2][x] = max(dp[j][k][3][2][x],dp[j][k][3][3][1-x]+2);
                }
            }
        }
        else if(c=='F'){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){
                    dp[0][3][j][k][x] = max(dp[0][3][j][k][x],dp[0][0][j][k][1-x]+1);

                    dp[1][3][j][k][x] = max(dp[1][3][j][k][x],dp[0][1][j][k][1-x]+2);
                    dp[1][3][j][k][x] = max(dp[1][3][j][k][x],dp[1][1][j][k][1-x]+2);
                    dp[1][3][j][k][x] = max(dp[1][3][j][k][x],dp[2][1][j][k][1-x]+3);
                    dp[1][3][j][k][x] = max(dp[1][3][j][k][x],dp[3][1][j][k][1-x]+2);

                    dp[2][3][j][k][x] = max(dp[2][3][j][k][x],dp[0][2][j][k][1-x]+2);
                    dp[2][3][j][k][x] = max(dp[2][3][j][k][x],dp[1][2][j][k][1-x]+3);
                    dp[2][3][j][k][x] = max(dp[2][3][j][k][x],dp[2][2][j][k][1-x]+2);
                    dp[2][3][j][k][x] = max(dp[2][3][j][k][x],dp[3][2][j][k][1-x]+2);

                    dp[3][3][j][k][x] = max(dp[3][3][j][k][x],dp[0][3][j][k][1-x]+1);
                    dp[3][3][j][k][x] = max(dp[3][3][j][k][x],dp[1][3][j][k][1-x]+2);
                    dp[3][3][j][k][x] = max(dp[3][3][j][k][x],dp[2][3][j][k][1-x]+2);
                    dp[3][3][j][k][x] = max(dp[3][3][j][k][x],dp[3][3][j][k][1-x]+1);

                    dp[j][k][0][3][x] = max(dp[j][k][0][3][x],dp[j][k][0][0][1-x]+1);

                    dp[j][k][1][3][x] = max(dp[j][k][1][3][x],dp[j][k][0][1][1-x]+2);
                    dp[j][k][1][3][x] = max(dp[j][k][1][3][x],dp[j][k][1][1][1-x]+2);
                    dp[j][k][1][3][x] = max(dp[j][k][1][3][x],dp[j][k][2][1][1-x]+3);
                    dp[j][k][1][3][x] = max(dp[j][k][1][3][x],dp[j][k][3][1][1-x]+2);

                    dp[j][k][2][3][x] = max(dp[j][k][2][3][x],dp[j][k][0][2][1-x]+2);
                    dp[j][k][2][3][x] = max(dp[j][k][2][3][x],dp[j][k][1][2][1-x]+3);
                    dp[j][k][2][3][x] = max(dp[j][k][2][3][x],dp[j][k][2][2][1-x]+2);
                    dp[j][k][2][3][x] = max(dp[j][k][2][3][x],dp[j][k][3][2][1-x]+2);

                    dp[j][k][3][3][x] = max(dp[j][k][3][3][x],dp[j][k][0][3][1-x]+1);
                    dp[j][k][3][3][x] = max(dp[j][k][3][3][x],dp[j][k][1][3][1-x]+2);
                    dp[j][k][3][3][x] = max(dp[j][k][3][3][x],dp[j][k][2][3][1-x]+2);
                    dp[j][k][3][3][x] = max(dp[j][k][3][3][x],dp[j][k][3][3][1-x]+1);
                }
            }
        }
    }
    int ans=0;
    int x = n%2;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                for(int l=0;l<4;l++)
                    ans = max(ans,dp[i][j][k][l][x]);
    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