제출 #514949

#제출 시각아이디문제언어결과실행 시간메모리
514949mzhJob Scheduling (CEOI12_jobs)C++17
0 / 100
248 ms3288 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...