Submission #655336

#	Time	Username	Problem	Language	Result	Execution time	Memory
655336		sword060	Miners (IOI07_miners)	C++17	100 / 100	286 ms	111668 KiB

miners

#include <bits/stdc++.h>
using namespace std;
int x,dp[100005][16][16];
map<char,int>mp;
string s;
int f(int a,int b){
  int l[4],r=0;
  l[0]=0;l[1]=0;l[2]=0;l[3]=0;
  l[a&3]++;l[a>>2]++;l[b]++;
  for(int i=1;i<=3;i++)r+=(l[i]>0);
  return r;
}
int rec(int i,int l,int r){
  if(i==x)return 0;
  if(~dp[i][l][r])return dp[i][l][r];
  int c1=f(l,mp[s[i]]),c2=f(r,mp[s[i]]);
  return dp[i][l][r]=max(rec(i+1,(l>>2)|(mp[s[i]]<<2),r)+c1,rec(i+1,l,(r>>2)|(mp[s[i]]<<2))+c2);
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  memset(dp,-1,sizeof(dp));
  mp['M']=1;mp['F']=2;mp['B']=3;
  cin>>x>>s;
  cout<<rec(0,0,0);
  return 0;
}

• 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