Submission #1070072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070072		erray	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	320 ms	87136 KiB

prison

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/debug.h"
#else 
  #define debug(...) void(37)
#endif

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, D, T;
  cin >> N >> D >> T;
  vector<int> t(N);
  for (int i = 0; i < N; ++i) {
    cin >> t[i];
  }
  auto F = [&](int i) {
    return T - t[i] + i; 
  };
  vector<int> par(N + 1, -1);
  vector<int> st, act;
  int rebels = 0;
  for (int i = 0; i < N; ++i) {
    if (t[i] <= T) {
      rebels += 1;
      while (!st.empty() && F(st.back()) <= F(i)) {
        st.pop_back();
      }
      st.push_back(i);
    } else {
      while (!st.empty() && i > F(st.back())) {
        st.pop_back();
      }
      if (!st.empty()) {
        rebels += 1;
        int l = st.back();
        debug(i, l);
        while (!act.empty() && act.back() > l) {
          par[act.back()] = i;
          act.pop_back();
        }
        act.push_back(i);
      }
    }
  }
  for (auto x : act) {
    par[x] = N;
  }
  vector<int> d(N + 1);
  for (int i = N - 1; i >= 0; --i) {
    if (par[i] != -1) {
      d[i] = d[par[i]] + 1;
    } 
  }
  debug(d);
  vector<int> ord(N + 1);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return d[x] < d[y];
  });
  vector<int> prio(N + 1);
  for (int i = 0; i <= N; ++i) {
    prio[ord[i]] = i;
  }
  debug(prio, ord);
  auto mx = prio;
  for (int i = 0; i < N; ++i) {
    if (par[i] != -1) {
      mx[par[i]] = max(mx[par[i]], mx[i]);
    }
  }
  debug(mx);
  vector<int> chain_len(N + 1);
  chain_len[N] = 1;
  for (int i = N - 1; i >= 0; --i) {
    if (par[i] != -1) {
      if (mx[par[i]] == mx[i]) {
        chain_len[i] = chain_len[par[i]] + 1;
      } else {
        chain_len[i] = 1;
      }
    }
  }
  debug(chain_len);
  vector<bool> is_leaf(N + 1, true);
  for (int i = 0; i < N; ++i) {
    if (par[i] != -1) {
      is_leaf[par[i]] = false;
    }
  }
  vector<int> take;
  for (int i = 0; i <= N; ++i) {
    if (is_leaf[i]) {
      take.push_back(chain_len[i]);
    }
  }
  debug(take);
  sort(take.rbegin(), take.rend());
  for (int i = 0; i < min(int(take.size()), D); ++i) {
    rebels -= take[i];
  }
  cout << rebels + 1 << '\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