Submission #223172

#	Time	Username	Problem	Language	Result	Execution time	Memory
223172		FieryPhoenix	Miners (IOI07_miners)	C++11	92 / 100	1027 ms	134900 KiB

miners

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N;
string S;
int dp[100001][13][13];
string str[30];
int t[30][3];

void fill(int ind, int a, int b, int c){
  t[ind][0]=a;
  t[ind][1]=b;
  t[ind][2]=c;
}

void precompute(){
  str[0]="!!"; fill(0,1,2,3);//t[0]={1,2,3}; 
  str[1]="!M"; fill(1,4,5,6);//t[1]={4,5,6};
  str[2]="!F"; fill(2,10,11,12);//t[2]={10,11,12};
  str[3]="!B"; fill(3,7,8,9);//t[3]={7,8,9};
  str[4]="MM"; fill(4,4,5,6);//t[4]={4,5,6};
  str[5]="MF"; fill(5,10,11,12);//t[5]={10,11,12};
  str[6]="MB"; fill(6,7,8,9);//t[6]={7,8,9};
  str[7]="BM"; fill(7,4,5,6);//t[7]={4,5,6};
  str[8]="BF"; fill(8,10,11,12);//t[8]={10,11,12};
  str[9]="BB"; fill(9,7,8,9);//t[9]={7,8,9};
  str[10]="FM"; fill(10,4,5,6);//t[10]={4,5,6};
  str[11]="FF"; fill(11,10,11,12);//t[11]={10,11,12};
  str[12]="FB"; fill(12,7,8,9);//t[12]={7,8,9};
}

bool used[4];

int calc(string s){
  used[0]=used[1]=used[2]=false;
  for (char c:s){
    if (c=='M') used[0]=true;
    else if (c=='F') used[1]=true;
    else if (c=='B') used[2]=true;
  }
  return used[0]+used[1]+used[2];
}

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  cin>>N>>S;
  S='?'+S;
  precompute();
  for (int i=0;i<=N+1;i++)
    for (int j=0;j<=12;j++)
      for (int k=0;k<=12;k++)
	dp[i][j][k]=-INF;
  dp[0][0][0]=0;
  for (int i=1;i<=N;i++){
    for (int j=0;j<=12;j++)
      for (int k=0;k<=12;k++){
	int cur;
	if (S[i]=='M') cur=0;
	else if (S[i]=='F') cur=1;
	else cur=2;
	//give mine 1
	dp[i][t[j][cur]][k]=max(dp[i][t[j][cur]][k],dp[i-1][j][k]+calc(str[j]+S[i]));
	dp[i][j][t[k][cur]]=max(dp[i][j][t[k][cur]],dp[i-1][j][k]+calc(str[k]+S[i]));
      }
  }
  int ans=0;
    for (int j=0;j<=12;j++)
      for (int k=0;k<=12;k++)
	ans=max(ans,dp[N][j][k]);
  cout<<ans<<endl;
  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: 0 / 8