Submission #147078

#	Time	Username	Problem	Language	Result	Execution time	Memory
147078		Sarah_Mokhtar	Miners (IOI07_miners)	C++14	100 / 100	1455 ms	110228 KiB

miners

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=2e5+100,OO=0x3f3f3f3f,mod=1e8;
int dp[N][4][4][4][4],n;
string s;
int diff(int x, int y, int z){
    set <int> ret = {x, y, z};
    while(*ret.rbegin() == 3){
        ret.erase(--ret.end());
    }
    return ret.size();
}
int id(char c){
    if(c=='M') return 0;
    if(c=='B') return 1;
    if(c=='F') return 2;
}
int solve(int i,int pl1,int pl2,int pr1,int pr2){
    if(i==n) return 0;
    int& ret=dp[i][pl1][pl2][pr1][pr2];
    if(~ret) return ret;
    int op1=diff(pl1,pl2,id(s[i]))+solve(i+1,pl2,id(s[i]),pr1,pr2);
    int op2=diff(id(s[i]),pr1,pr2)+solve(i+1,pl1,pl2,pr2,id(s[i]));
    return ret=max(op1,op2);
}
int main(){
    cin>>n>>s;
    memset(dp,-1,sizeof(dp));
    cout<<solve(0,3,3,3,3);
}

Compilation message (stderr)

miners.cpp: In function 'int id(char)':
miners.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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