제출 #1132289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132289		rxlfd314	The short shank; Redemption (BOI21_prison)	C++20	100 / 100	324 ms	251612 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
template<class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N, D, T;
  cin >> N >> D >> T;
  vt<int> A(N), L(N, -1), parent(N+1, -1), sk;
  vt<ari2> sk2;
  vt<vt<int>> adj(N+1);
  int ans = 0, nodes = 0;
  FOR(i, 0, N-1) {
    cin >> A[i];
    if (A[i] > T) {
      while (size(sk) && i > T + sk.back() - A[sk.back()])
        sk.pop_back();
      if (!size(sk))
        ans++;
      else {
        L[i] = sk.back();
        nodes++;
        while (size(sk2) && sk2.back()[0] > L[i]) {
          const auto [_, n] = sk2.back();
          sk2.pop_back();
          adj[nodes].push_back(n);
          parent[n] = nodes;
        }
        sk2.push_back({i, nodes});
      }
    } else {
      while (size(sk) && i - A[i] >= sk.back() - A[sk.back()])
        sk.pop_back();
      sk.push_back(i);
    }
  }
  for (const auto &[_, i] : sk2)
    adj[0].push_back(i), parent[i] = 0;
  #ifdef DEBUG
  FOR(i, 0, N-1)
    cout << L[i] << "\n "[i+1<N];
  FOR(i, 0, nodes)
    for (const auto &j : adj[i])
      cout << "edge " << i << ' ' << j << '\n';
  FOR(i, 0, nodes)
    cout << parent[i] << "\n "[i<nodes];
  #endif
  
  vt<ari2> max_depth(nodes+1);
  vt<int> depth(nodes+1);
  function<void(int, int)> dfs = [&](const int i, const int d) {
    max_depth[i] = {d, i};
    depth[i] = d;
    for (const auto &j : adj[i]) {
      dfs(j, d + 1);
      max_depth[i] = max(max_depth[i], max_depth[j]);
    }
  };
  dfs(0, 0);
  priority_queue<ari2> pq;
  pq.push(max_depth[0]);
  vt<int> dead(nodes+1);
  while (size(pq) && D--) {
    auto [d, i] = pq.top();
    pq.pop();
    ans += d;
    for (; !dead[i] && i >= 0; i = parent[i]) {
      dead[i] = 1;
      for (const auto &j : adj[i])
        if (!dead[j])
          pq.push({max_depth[j][0] - depth[i], max_depth[j][1]});
    }
  }
  
  cout << N - ans << '\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