Submission #1220700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220700		lopkus	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	426 ms	4000 KiB

jobs

#include <bits/stdc++.h>

int main() {

  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, d, m;
  std::cin >> n >> d >> m;
  std::vector<int> a(m + 1);
  for(int i = 1; i <= m; i++) {
    std::cin >> a[i];
  }
  std::sort(a.begin() + 1, a.end());
  int l = 1, r = m, ans = - 1;
  while(l <= r) {
    int mid = (l + r) / 2;
    std::set<int> st;
    for(int i = 1; i <= mid; i++) {
      st.insert(a[i]);
    }
    int ok = 1;
    for(int i = mid + 1; i <= m; i++) {
      auto it = st.begin();
      if(*it < a[i]) {
        int old = *it;
        int New = std::max(old + 1, a[i]);
        if(New > a[i] + d) {
          ok = 0;
          break;
        }
        st.insert(New);
        st.erase(it);
      }
      else {
        ok = 0;
        break;
      }
    }
    if(ok) {
      r = mid - 1;
      ans = mid;
    }
    else {
      l = mid + 1;
    }
  }
  std::cout << ans;
}

/**



**/

• Subtask 1: 0 / 100