Submission #1022629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022629		ttamx	Miners (IOI07_miners)	C++17	100 / 100	180 ms	100944 KiB

miners

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;
const int INF=INT_MAX/2;

int n;
int dp[N][4][4][4][4];
string s;
int ans;

int calc(int a,int b,int c){
    if(a==0)return (b==0||b==c)?1:2;
    if(a==b&&a==c)return 1;
    if(a==b||a==c||b==c)return 2;
    return 3;
}

void chmax(int &x,int v){
    if(v>x)x=v;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    cin >> s;
    for(int i=0;i<=n;i++){
        for(int x=0;x<4;x++){
            for(int y=0;y<4;y++){
                for(int z=0;z<4;z++){
                    for(int w=0;w<4;w++){
                        dp[i][x][y][z][w]=-INF;
                    }
                }
            }
        }
    }
    dp[0][0][0][0][0]=0;
    for(int i=0;i<n;i++){
        int v=s[i]=='M'?1:s[i]=='F'?2:3;
        for(int x=0;x<4;x++){
            for(int y=0;y<4;y++){
                for(int z=0;z<4;z++){
                    for(int w=0;w<4;w++){
                        chmax(dp[i+1][x][y][w][v],dp[i][x][y][z][w]+calc(z,w,v));
                        chmax(dp[i+1][y][v][z][w],dp[i][x][y][z][w]+calc(x,y,v));
                    }
                }
            }
        }
    }
    for(int x=0;x<4;x++){
        for(int y=0;y<4;y++){
            for(int z=0;z<4;z++){
                for(int w=0;w<4;w++){
                    chmax(ans,dp[n][x][y][z][w]);
                }
            }
        }
    }
    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