oj.uz

Submission #655337

# Submission time Handle Problem Language Result Execution time Memory
655337 2022-11-03T21:07:37 Z sword060 Miners (IOI07_miners) C++17
100 / 100
 358 ms 512 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 212 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 344 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 340 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 492 KB Output is correct

Subtask #12
8.0 / 8.0

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