제출 #501057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501057		600Mihnea	Miners (IOI07_miners)	C++17	84 / 100	1595 ms	126016 KiB

miners

#include <bits/stdc++.h>

using namespace std;

vector<int> operator + (vector<int> a, vector<int> b) {
  for (auto &x : b) {
    a.push_back(x);
  }
  return a;
}

vector<int> join(vector<int> a, vector<int> b) {
  return a + vector<int> {-1} + b;
}

pair<vector<int>, vector<int>> split(vector<int> a) {
  vector<int> x, y;
  int cnt = 0;
  for (auto &it : a) {
    if (it == -1) {
      cnt++;
      continue;
    }
    if (cnt == 0) {
      x.push_back(it);
    } else {
      y.push_back(it);
    }
  }
  assert(cnt == 1);
  return {x, y};
}

void upd(int pos, vector<int> a, vector<int> b, int value, vector<map<vector<int>, int>> &dp) {
  vector<int> state = join(a, b);
  if (!dp[pos].count(state)) {
    dp[pos][state] = value;
  } else {
    dp[pos][state] = max(dp[pos][state], value);
  }
}

int eval(vector<int> a) {
  set<int> S;
  for (auto &x : a) {
    S.insert(x);
  }
  return (int) S.size();
}


vector<int> add(vector<int> a, int x) {
  if ((int) a.size() == 2) {
    a = {a[1], x};
    return a;
  }
  assert((int) a.size() <= 1);
  a.push_back(x);
  return a;
}

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

  int n;
  string s;
  cin >> n >> s;

  vector<map<vector<int>, int>> dp(n + 1);
  upd(0, {}, {}, 0, dp);

  for (int i = 0; i < n; i++) {
    for (auto &v : dp[i]) {
      auto it = split(v.first);
      vector<int> a = it.first, b = it.second;
      upd(i + 1, add(a, s[i]), b, v.second + eval(a + vector<int> {s[i]}), dp);
      upd(i + 1, a, add(b, s[i]), v.second + eval(b + vector<int> {s[i]}), dp);
    }
  }
  int best = -1;
  for (auto &it : dp[n]) {
    best = max(best, it.second);
  }
  cout << best << "\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: 0 / 8
• Subtask 12: 0 / 8