Submission #721441

#	Time	Username	Problem	Language	Result	Execution time	Memory
721441		Yell0	Miners (IOI07_miners)	C++17	74 / 100	171 ms	1016 KiB

miners

#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][j][a[i]][l][m],dp[i&1][j][k][l][a[i]]});
          }
  cout<<ans<<'\n';
  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 0 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8