Submission #1208887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208887		aykhn	The short shank; Redemption (BOI21_prison)	C++20	100 / 100	159 ms	41676 KiB

prison

#include<bits/stdc++.h>

using namespace std;

const int MXN = 2e6 + 5;
const int LOG = 20;

int n, D, T, res;
int arr[MXN], L[MXN], val[MXN], cnt[MXN];
array<int, 2> mx[MXN];

void _()
{
  cin >> n >> D >> T;
  res = n;
  for (int i = 1; i <= n; i++) cin >> arr[i];
  {
    vector<int> v;
    for (int i = 1; i <= n; i++)
    {
      while (!v.empty() && arr[i] - i <= arr[v.back()] - v.back()) v.pop_back();
      v.push_back(i);
      while (!v.empty() && arr[v.back()] - v.back() > T - i) v.pop_back();
      if (!v.empty()) L[i] = v.back();
    }
  }
  vector<int> v;
  for (int i = 1; i <= n; i++)
  {
    if (!L[i]) 
    {
      res--;
      continue;
    }
    if (L[i] == i) continue;
    mx[i] = {0, i};
    while (!v.empty() && L[v.back()] >= L[i]) 
    {
      mx[i] = max(mx[i], {mx[v.back()][0] + 1, mx[v.back()][1]});
      v.pop_back();
    }
    v.push_back(i);
    val[mx[i][1]]++;
  }
  for (int i = 1; i <= n; i++) cnt[val[i]]++;
  for (int i = n; i >= 1; i--)
  {
    while (cnt[i] && D) res -= i, cnt[i]--, D--;
  }
  cout << res << '\n';
}
signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

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