제출 #1007286

#제출 시각아이디문제언어결과실행 시간메모리
1007286DON_FJob Scheduling (CEOI12_jobs)C++14
55 / 100
125 ms11088 KiB
#include <bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; ++i){
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a.begin(), a.end());
	auto Work = [&](int num){
		int j = 0;
		for (int day = 1; day <= n; ++day){
			int k = 0;
			while (j < m && k < num){
				if (day > a[j].first + d){
					return false;
				}
				++j;
				++k;
			}
		}
		return (j == m);
	};
	int lo = 1, hi = m, ans = -1;
	while (lo <= hi){
		int mid = lo + (hi - lo) / 2;
		if (Work(mid)){
			ans = mid;
			hi = mid - 1;
		}else{
			lo = mid + 1;
		}
	}
    cout << ans << "\n";
    for (int i = 0; i < n; ++i){
		cout << "0\n";
	}
    /*int j = 0;
    for (int i = 0; i < n; ++i){
		int k = 0;
		while (k < ans && j < m){
			cout << a[j].second + 1 << " ";
			++j;
			++k;
		}
		cout << "0\n";
	}*/
	/*
	8 2 12
	1 2 4 2 1 3 5 6 2 3 6 4
	*/
} 
#Verdict Execution timeMemoryGrader output
Fetching results...