Submission #776936

#	Time	Username	Problem	Language	Result	Execution time	Memory
776936		tch1cherin	The short shank; Redemption (BOI21_prison)	C++17	15 / 100	2077 ms	9044 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> t(n);
  for (int &v : t) {
    cin >> v;
  }
  vector<int> l(n, n);
  for (int i = 0; i < n; i++) {
    for (int j = i; j >= 0; j--) {
      if (j + T - t[j] >= i) {
        l[i] = j;
        break;
      }      
    }
  }
  for (int i = 0; i < d; i++) {
    pair<int, int> ans = {0, 0}; 
    for (int L = n - 1; L >= 0; L--) {
      int cnt = 0;
      for (int x = L; x < n; x++) {
        if (l[x] < L) {
          cnt++;
        } 
      }
      ans = max(ans, {cnt, L});
    }
    for (int x = ans.second; x < n; x++) {
      if (l[x] < ans.second) {
        l[x] = n;
      }
    }
  }
  cout << n - count(l.begin(), l.end(), n) << "\n";
}

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