Submission #655337

#	Time	Username	Problem	Language	Result	Execution time	Memory
655337		sword060	Miners (IOI07_miners)	C++17	100 / 100	358 ms	512 KiB

miners

#include <bits/stdc++.h>
using namespace std;
int x,dp[2][16][16];
string s;
int p(char c){
  if(c=='M')return 1;
  if(c=='F')return 2;
  return 3;
}
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 main(){
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>x>>s;
  for(int i=0;i<=1;i++)
    for(int j=0;j<16;j++)
      for(int k=0;k<16;k++)
        dp[i][j][k]=-1e9;
  dp[0][0][0]=0;
  int c=0;
  for(int i=0;i<x;i++){
    for(int j=0;j<16;j++){
      for(int k=0;k<16;k++){
        int c1=f(j,p(s[i])),c2=f(k,p(s[i]));
        dp[c^1][(j>>2)|(p(s[i])<<2)][k]=max(dp[c^1][(j>>2)|(p(s[i])<<2)][k],dp[c][j][k]+c1);
        dp[c^1][j][(k>>2)|(p(s[i])<<2)]=max(dp[c^1][j][(k>>2)|(p(s[i])<<2)],dp[c][j][k]+c2);
      }
    }
    c^=1;
  }
  int ans=0;
  for(int i=0;i<16;i++)
    for(int j=0;j<16;j++)
      ans=max(ans,dp[c][i][j]);
  cout<<ans;
  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