oj.uz

Submission #390066

# Submission time Handle Problem Language Result Execution time Memory
390066 2021-04-15T09:14:31 Z tushar_2658 Miners (IOI07_miners) C++14
100 / 100
 1264 ms 230060 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 100005;

int dp[maxn][4][4][4][4], vis[maxn][4][4][4][4];
int n;
int a[maxn];
string s;

int call(int cur, int last, int last1, int lst, int lst1){
  if(cur >= n)return 0;
  if(vis[cur][last][last1][lst][lst1])return dp[cur][last][last1][lst][lst1];
  vis[cur][last][last1][lst][lst1] = 1;
  int ret = 0;
  if(last != 0 && last1 != 0){
    set<int> ms;
    ms.insert(a[cur]);
    ms.insert(last);
    ms.insert(last1);
    int cnt = ms.size();
    ret = max(ret, call(cur + 1, a[cur], last, lst, lst1) + cnt);
  }else if(last != 0){
    set<int> ms;
    ms.insert(a[cur]);
    ms.insert(last);
    int cnt = ms.size();
    ret = max(ret, call(cur + 1, a[cur], last, lst, lst1) + cnt);
  }else {
    ret = max(ret, call(cur + 1, a[cur], last, lst, lst1) + 1);
  }
  if(lst != 0 && lst1 != 0){
    set<int> ms;
    ms.insert(a[cur]);
    ms.insert(lst);
    ms.insert(lst1);
    int cnt = ms.size();
    ret = max(ret, call(cur + 1, last, last1, a[cur], lst) + cnt);
  }else if(lst != 0){
    set<int> ms;
    ms.insert(a[cur]);
    ms.insert(lst);
    int cnt = ms.size();
    ret = max(ret, call(cur + 1, last, last1, a[cur], lst) + cnt);
  }else {
    ret = max(ret, call(cur + 1, last, last1, a[cur], lst) + 1);
  }
  return dp[cur][last][last1][lst][lst1] = ret;
}

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  cin >> s;
  for(int i = 0; i < n; ++i){
    if(s[i] == 'M')a[i] = 1;
    else if(s[i] == 'B')a[i] = 2;
    else a[i] = 3;
  }
  cout << call(0, 0, 0, 0, 0) << '\n';

  return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2508 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11512 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 23308 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 56908 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 167100 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1264 ms 230060 KB Output is correct