Submission #159460

#	Time	Username	Problem	Language	Result	Execution time	Memory
159460		InfiniteJest	Miners (IOI07_miners)	C++14	100 / 100	249 ms	108792 KiB

miners

#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);


}

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