Submission #900297

#	Time	Username	Problem	Language	Result	Execution time	Memory
900297		NeroZein	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	2087 ms	12708 KiB

prison

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e6 + 6;

int a[N];
int ct[N];
int low[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, d, t;
  cin >> n >> d >> t;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  stack<int> stk;
  for (int i = 1; i <= n; ++i) {
    stk.push(i);
    while (!stk.empty() && a[stk.top()] + i - stk.top() > t) {
      stk.pop();
    }
    low[i] = (stk.empty() ? n + 1 : stk.top());
  }
  for (int iter = 1; iter <= d; ++iter) {
    int mx = 1; 
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        if (low[j] < i) {
          ct[i]++;
          if (ct[i] > ct[mx]) {
            mx = i; 
          } 
        }
      }
    }
    for (int i = 1; i <= n; ++i) {
      for (int j = i; j <= n; ++j) {
        if (low[j] < i) {
          ct[i]--;
        }
      }
    }
    for (int j = mx; j <= n; ++j) {
      if (low[j] < mx) {
        low[j] = n + 1; 
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (low[i] <= n) {
      ans++;
    }
  }
  cout << ans << '\n';
  return 0;
}

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