Submission #514949

#	Time	Username	Problem	Language	Result	Execution time	Memory
514949		mzh	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	248 ms	3288 KiB

jobs

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, d, m;
  cin >> n >> d >> m;
  vector<int> ti(n);
  for (int &x : ti) {
    cin >> x;
  }
  sort(ti.begin(), ti.end());
  int l = 0, r = n;
  while (l + 1 < r) {
    int mid = l + (r - l) / 2;
    // Next availible times for machines
    multiset<int> st;
    for (int i = 0; i < mid; i++) {
      st.insert(0);
    }
    bool ok = true;
    for (int i = 0; i < n; i++) {
      // We want to use the largest number <= ti[i] + d
      auto lb = st.lower_bound(ti[i] + d);
      if (lb == st.end()) {
        lb--;
      }
      if (lb != st.begin()) {
        lb--;
        st.erase(lb);
        st.insert(max(*lb, ti[i]) + 1);
      } else {
        ok = false;
        break;
      }
    }
    (ok ? r : l) = mid;
  }
  cout << r << '\n';
}

• Subtask 1: 0 / 100