oj.uz

Submission #581557

# Submission time Handle Problem Language Result Execution time Memory
581557 2022-06-22T18:12:38 Z HeyYouNotYouYou Miners (IOI07_miners) C++14
0 / 100
 219 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 200 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 219 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 210 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 193 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 206 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -