제출 #1366402

#제출 시각아이디문제언어결과실행 시간메모리
1366402tuncay_pashaJob Scheduling (CEOI12_jobs)C++20
0 / 100
51 ms8268 KiB
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define pasha ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(v) begin(v), end(v)
using namespace std;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 1e+5 + 5, oo = 2e+18;

void _() {
  int n, d, m; cin >> n >> d >> m;
  vector<int> a(m);
  vector<int> f(n + 1, 0);
  for (int i = 0; i < m; ++i) {
    cin >> a[i];
    ++f[a[i]];
  }
  int lo = 1, hi = m, ans = m;
  while (lo <= hi) {
    int mid = (lo + hi) >> 1;
    queue<int> q;
    bool ok = true;
    for (int i = 1; i <= n; ++i) {
      int x = f[i];
      while (x--) q.push(i);
      for (int j = 0; j < mid && !q.empty(); ++j) {
        if (i > q.front() + d) {
          ok = false;
          break;
        }
        q.pop();
      }
      if (!ok) break;
    }
    ok &= q.empty();
    if (ok) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  cout << ans << '\n';
}

signed main() {
  pasha
  int t = 1;
  // cin >> t;
  for (int cs = 1; cs <= t; ++cs) {
    _();
    // cout << '\n';
  }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…