제출 #390066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390066		tushar_2658	Miners (IOI07_miners)	C++14	100 / 100	1264 ms	230060 KiB

miners

#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 / 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