oj.uz

Submission #159460

# Submission time Handle Problem Language Result Execution time Memory
159460 2019-10-22T19:40:57 Z InfiniteJest Miners (IOI07_miners) C++14
100 / 100
 249 ms 108792 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1400 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5880 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11256 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 27536 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 81812 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 108792 KB Output is correct