Submission #1245775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245775		warrenn	Miners (IOI07_miners)	C++20	100 / 100	223 ms	210412 KiB

miners

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

int n;
string s;
int dp[100002][4][4][4][4];

int coal(int a,int b,int c){
    int cnt[4];
    cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
    cnt[a]++;
    cnt[b]++;
    cnt[c]++;

    if(cnt[1]==1 && cnt[2]==1 && cnt[3]==1)return 3;
    if(cnt[1]>=1){
        if(cnt[2]>=1 || cnt[3]>=1)return 2;
        return 1;
    }
    if(cnt[2]>=1){
        if(cnt[1]>=1 || cnt[3]>=1)return 2;
        return 1;
    }
    if(cnt[3]>=1){
        if(cnt[2]>=1 || cnt[1]>=1)return 2;
        return 1;
    }
    return 1;
}

int conv(char a){
    if(a=='M')return 1;
    if(a=='B')return 2;
    if(a=='F')return 3;
    return 0;
}

int f(int idx,int a,int b,int c,int d){
    if(idx==n+1)return 0;
    if(dp[idx][a][b][c][d]!=-1)return dp[idx][a][b][c][d];
    int res=0;
    res=max(res,f(idx+1,b,conv(s[idx-1]),c,d)+coal(a,b,conv(s[idx-1])));
    res=max(res,f(idx+1,a,b,d,conv(s[idx-1]))+coal(c,d,conv(s[idx-1])));
    return dp[idx][a][b][c][d]=res;
}

signed main(){
    cin>>n>>s;
    memset(dp,-1,sizeof dp);
    cout<<f(1,0,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