Submission #1198152

#TimeUsernameProblemLanguageResultExecution timeMemory
1198152orgiloogiiJob Scheduling (CEOI12_jobs)C++20
0 / 100
1096 ms7232 KiB
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	int n, d, m;
	cin >> n >> d >> m;
	vector <pair <int, int>> reg(m + 1);
	for (int i = 1;i <= m;i++) {
		cin >> reg[i].first;
		reg[i].second = i;
	}
	sort(reg.begin(), reg.end());
	int l = 1, r = 1e9;
	while (l + 1 < r) {
		int mid = (l + r) / 2;
		bool pos = true;
		int day = 1;
		for (int i = 1;i <= m;) {
			int cnt = mid;
			while (cnt && i <= m) {
				if (reg[i].first > day) break;
				if (reg[i].first + d < day) {
					pos = false;
					break;
				}
				i++;
				cnt--;
			}
			day++;
		}
		if (pos) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	cout << r << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...