oj.uz

Submission #501058

# Submission time Handle Problem Language Result Execution time Memory
501058 2022-01-02T10:09:16 Z 600Mihnea Miners (IOI07_miners) C++17
84 / 100
 1500 ms 119600 KB 
#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) {
  if (a > b) swap(a, 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 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 204 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 204 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1542 ms 116360 KB Time limit exceeded

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 119600 KB Time limit exceeded