oj.uz

Submission #223174

# Submission time Handle Problem Language Result Execution time Memory
223174 2020-04-15T02:50:57 Z FieryPhoenix Miners (IOI07_miners) C++11
100 / 100
 1395 ms 628 KB 
#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[11][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);
  int ans=0;
  cin>>N>>S;
  S='?'+S;
  precompute();
  for (int i=0;i<=10;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;
  int I=1;
  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]));
      }
    }
    for (int j=0;j<=12;j++)
      for (int k=0;k<=12;k++)
	ans=max(ans,dp[I][j][k]);
    if (I==10){
      for (int j=0;j<=12;j++)
	for (int k=0;k<=12;k++)
	  dp[0][j][k]=dp[10][j][k];
      for (int l=1;l<=10;l++)
	for (int j=0;j<=12;j++)
	  for (int k=0;k<=12;k++)
	    dp[l][j][k]=-INF;
      I=0;
    }
    I++;
  }
  cout<<ans<<endl;
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 388 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 400 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 428 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 628 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1395 ms 512 KB Output is correct