oj.uz

Submission #581583

# Submission time Handle Problem Language Result Execution time Memory
581583 2022-06-22T19:17:54 Z HeyYouNotYouYou Miners (IOI07_miners) C++14
0 / 100
 1143 ms 210356 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][4][4][4][4];
int check(int a,int b,int c){
  set<int>st;
  if(a!=0) st.insert(a);
  if(b!=0) st.insert(b);
  if(c!=0) st.insert(c);
  return st.size();
}
int solve(int i,int preva1,int prevb1,int preva2,int prevb2)
{
  //cout<<i<<" "<<state1<<" "<<state2<<endl;
  if(i==n) return 0;
  int ans=0;
  if(dp[i][preva1][prevb1][preva2][prevb2]!=-1) return dp[i][preva1][prevb1][preva2][prevb2];
  int x; if(s[i]=='M') x=1; else if(s[i]=='B') x=2; else x=3;
  ans=solve(i+1,preva1,preva2,prevb2,x)+check(preva2,prevb2,x);
  ans=max(ans,solve(i+1,prevb1,x,preva2,prevb2)+check(preva1,prevb1,x));
  return dp[i][preva1][prevb1][preva2][prevb2]=ans;
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n ;
  cin>>s;
  memset(dp,-1,sizeof dp);
  cout<<solve(0,0,0,0,0)-1;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 200568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 200648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 200560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 200600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 200564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 200652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 200648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 201052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 201632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 203092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 577 ms 207908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1143 ms 210356 KB Output isn't correct
2 Halted 0 ms 0 KB -