Submission #581557

#	Time	Username	Problem	Language	Result	Execution time	Memory
581557		HeyYouNotYouYou	Miners (IOI07_miners)	C++14	0 / 100	219 ms	524288 KiB

miners

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 100001,INF=1e12;
int n;
string s;
int dp[N][3][3][3][3][3][3];
int solve(int i,int M1,int B1,int F1,int M2,int B2,int F2)
{
  //cout<<i<<" "<<M1<<" "<<B1<<" "<<F1<<" "<<M2<<" "<<B2<<" "<<F2<<endl;
  if(i==n) return 0;
  int ans=0;
  if(M1!=-1&&B1!=-1&&F1!=-1&&M2!=-1&&B2!=-1&&F2!=-1&&dp[i][M1][B1][F1][M2][B2][F2]!=-1) return dp[i][M1][B1][F1][M2][B2][F2];

  if(s[i]=='M'){
    int m1=M1,b1=B1,f1=F1;
    m1=0,b1++,f1++;
    if(B1==-1 || b1>2) b1=-1;
    if(F1==-1 || f1>2) f1=-1;
    ans = solve(i+1,m1,b1,f1,M2,B2,F2)+((m1>=0)+(b1>=0)+(f1>=0));

    m1=M2,b1=B2,f1=F2;
    m1=0,b1++,f1++;
    if(B2==-1 || b1>2) b1=-1;
    if(F2==-1 || f1>2) f1=-1;
    ans=max(ans,solve(i+1,M1,B1,F1,m1,b1,f1)+((m1>=0)+(b1>=0)+(f1>=0)));
  }
  else if(s[i]=='B'){
    int m1=M1,b1=B1,f1=F1;
    m1++,b1=0,f1++;
    if(M1==-1 || m1>2) m1=-1;
    if(F1==-1 || f1>2) f1=-1;
    ans = solve(i+1,m1,b1,f1,M2,B2,F2)+((m1>=0)+(b1>=0)+(f1>=0));

    m1=M2,b1=B2,f1=F2;
    m1++,b1=0,f1++;
    if(M2==-1 || m1>2) m1=-1;
    if(F2==-1 || f1>2) f1=-1;
    ans=max(ans,solve(i+1,M1,B1,F1,m1,b1,f1)+((m1>=0)+(b1>=0)+(f1>=0)));
  }
  else if(s[i]=='F'){
    int m1=M1,b1=B1,f1=F1;
    m1++,b1++,f1=0;
    if(M1==-1 || m1>2) m1=-1;
    if(B1==-1 || b1>2) b1=-1;
    ans = solve(i+1,m1,b1,f1,M2,B2,F2)+((m1>=0)+(b1>=0)+(f1>=0));

    m1=M2,b1=B2,f1=F2;
    m1++,b1++,f1=0;
    if(M2==-1 || m1>2) m1=-1;
    if(B2==-1 || b1>2) b1=-1;
    ans=max(ans,solve(i+1,M1,B1,F1,m1,b1,f1)+((m1>=0)+(b1>=0)+(f1>=0)));
  }
  if(M1!=-1&&B1!=-1&&F1!=-1&&M2!=-1&&B2!=-1&&F2!=-1)
  return dp[i][M1][B1][F1][M2][B2][F2]=ans;
  else return ans;
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n ;
  cin>>s;
  memset(dp,-1,sizeof dp);
  cout<<solve(0,-1,-1,-1,-1,-1,-1);
}

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