제출 #1366396

#제출 시각아이디문제언어결과실행 시간메모리
1366396tuncay_pashaJob Scheduling (CEOI12_jobs)C++20
0 / 100
43 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 = n, ans = n;
  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);
      if (!q.empty()) {
        for (int j = 0; j < mid && !q.empty(); ++j) {
          if (i >= q.front() + d) {
            ok = false;
            break;
          }
          q.pop();
        }
        if (!ok) break;
        if (q.empty()) {
          continue;
        }
      }
      if (!ok) break;
    }
    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';
  }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…