Submission #1080775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080775		juicy	Miners (IOI07_miners)	C++17	100 / 100	730 ms	108960 KiB

miners

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const char key[] = {'M', 'B', 'F'};

const int N = 1e5;

int n;
int A[N];
int dp[N][4][4][4][4];

int count(int a, int b, int c) {
  vector<int> k;
  for (auto x : {a, b, c}) {
    if (x < 3) {
      k.push_back(x);
    }
  }
  sort(k.begin(), k.end());
  return unique(k.begin(), k.end()) - k.begin();
}

int f(int i, int a, int b, int x, int y) {
  if (i == n) {
    return 0;
  }
  int &res = dp[i][a][b][x][y];
  if (~res) {
    return res;
  }
  int c = A[i];
  res = f(i + 1, b, c, x, y) + count(a, b, c);
  res = max(res, f(i + 1, a, b, y, c) + count(x, y, c));
  return res;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n; ++i) {
    char c; cin >> c;
    A[i] = find(key, key + 3, c) - key;
  }
  memset(dp, -1, sizeof(dp));
  cout << f(0, 3, 3, 3, 3);
  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