Submission #1220702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220702		lopkus	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	1096 ms	24876 KiB

jobs

#include <bits/stdc++.h>

#define int int32_t

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());
  for(int i = 1; i <= m; i++) {
    //std::cout << a[i] << " ";
  }
  //std::cout << "\n";
  int l = 1, r = m, ans = - 1;
  while(l <= r) {
    int mid = (l + r) / 2;
    std::multiset<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();
      int old = *it;
      int New = std::max(old + 1, a[i]);
      //std::cout << i << " " << New << "\n";
      if(New > a[i] + d) {
        ok = 0;
        break;
      }
      st.erase(st.find(*it));
      st.insert(New);
    }
    if(ok) {
      r = mid - 1;
      ans = mid;
    }
    else {
      l = mid + 1;
    }
  }
  std::cout << ans;
}

/**

8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

**/

• Subtask 1: 0 / 100