oj.uz

Submission #721442

# Submission time Handle Problem Language Result Execution time Memory
721442 2023-04-11T00:44:11 Z Yell0 Miners (IOI07_miners) C++17
100 / 100
 126 ms 904 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int MN=1e5+2;
int N,dp[2][4][4][4][4],a[MN];
string s;

inline int calc(char x,char y,char z) {
  return (x==1||y==1||z==1)+(x==2||y==2||z==2)+(x==3||y==3||z==3);
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>N>>s;
  for(int i=0;i<N;++i) {
    if(s[i]=='B') a[i+1]=1;
    if(s[i]=='F') a[i+1]=2;
    if(s[i]=='M') a[i+1]=3;
  }
  for(int i=0;i<2;++i) for(int j=0;j<4;++j) for(int k=0;k<4;++k) for(int l=0;l<4;++l) for(int m=0;m<4;++m) dp[i][j][k][l][m]=INT_MIN;
  dp[0][0][0][0][0]=0;
  int ans=0;
  for(int i=1;i<=N;++i)
    for(int j=0;j<4;++j)
      for(int k=0;k<4;++k)
        for(int l=0;l<4;++l)
          for(int m=0;m<4;++m) {
            dp[i&1][k][a[i]][l][m]=max(dp[i&1][k][a[i]][l][m],dp[(i-1)&1][j][k][l][m]+calc(a[i],j,k));
            dp[i&1][j][k][m][a[i]]=max(dp[i&1][j][k][m][a[i]],dp[(i-1)&1][j][k][l][m]+calc(a[i],l,m));
            ans=max({ans,dp[i&1][k][a[i]][l][m],dp[i&1][j][k][m][a[i]]});
          }
  cout<<ans<<'\n';
  return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 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 1 ms 212 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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