Submission #825176

#	Time	Username	Problem	Language	Result	Execution time	Memory
825176		tch1cherin	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	415 ms	55516 KiB

prison

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, D, T;
  cin >> N >> D >> T;
  vector<int> pi(N, N);
  stack<pair<int, int>> S;
  int max_r = -1;
  int active = 0, passive = 0;
  for (int i = 0; i < N; i++) {
    int t;
    cin >> t;
    active += t <= T;
    max_r = max(max_r, i + T - t);
    if (!S.empty()) {
      S.top().second = max(S.top().second, i + T - t);
    }
    if (t > T && i <= max_r) {
      passive++;
      pi[i] = N;
      while (!S.empty() && S.top().second < i) {
        pi[S.top().first] = i;
        S.pop();
      }
      S.emplace(i, -1);
    } else {
      pi[i] = -1;
    }
  }
  vector<int> depth(N + 1, -1);
  depth[N] = 0;
  for (int i = N - 1; i >= 0; i--) {
    if (pi[i] != -1) {
      depth[i] = depth[pi[i]] + 1;
    }
  }
  vector<int> ord(N);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return depth[i] > depth[j];
  });
  vector<int> c(N);
  vector<bool> used(N);
  for (int i : ord) {
    if (pi[i] == -1) {
      continue;
    }
    int j = i;
    while (j < N && !used[j]) {
      c[i]++;
      used[j] = true;
      j = pi[j];
    }
  }
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return c[i] > c[j];
  });
  used.assign(N, false);
  int sum = 0;
  for (int k = 0; k < D; k++) {
    int i = ord[k];
    if (pi[i] == -1) {
      continue;
    }
    int j = i;
    while (j < N && !used[j]) {
      sum++;
      used[j] = true;
      j = pi[j];
    }
  }
  cout << active + passive - sum << "\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 20 / 20