Submission #159460

#TimeUsernameProblemLanguageResultExecution timeMemory
159460InfiniteJestMiners (IOI07_miners)C++14
100 / 100
249 ms108792 KiB
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <map>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;

int n;
int v[100001];
int dp[100001][4][4][4][4];

int funz(int a, int b, int c){
  if(b==3&&c==3){
    b=a;
    c=a;
  }
  else if(c==3&&b!=3){
    c=a;
  }
  if(a!=b&&b!=c&&a!=c)return 3;
  if(a==b&&b!=c)return 2;
  if(a==b&&b==c)return 1;
  if(a==c&&c!=b)return 2;
  return 2;
}

int rec(int pos, int a1, int a2, int b1, int b2){
  if(pos==n)return 0;
  if(dp[pos][a1][a2][b1][b2]!=-1)return dp[pos][a1][a2][b1][b2];
  dp[pos][a1][a2][b1][b2]=max(funz(v[pos],a1,a2)+rec(pos+1,v[pos],a1,b1,b2),funz(v[pos],b1,b2)+rec(pos+1,a1,a2,v[pos],b1));
  //cout<<"pos "<<pos<<" a1 "<<a1<<" a2 "<<a2<<" b1 "<<b1<<" b2 "<<b2<<" dp "<<dp[pos][a1][a2][b1][b2]<<endl;
  return dp[pos][a1][a2][b1][b2];
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    char g; cin>>g;
    if(g=='B')v[i]=0;
    else if(g=='M')v[i]=1;
    else if(g=='F')v[i]=2;
  }
  for(int i=0;i<n;i++){
    for(int y=0;y<4;y++){
      for(int j=0;j<4;j++){
        for(int u=0;u<4;u++){
          for(int h=0;h<4;h++){
            dp[i][y][j][u][h]=-1;
          }
        }
      }
    }
  }
  cout<<rec(0,3,3,3,3);


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...