Submission #692524

#	Time	Username	Problem	Language	Result	Execution time	Memory
692524		Snowmanonahoe	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	80 ms	7892 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
struct day {
	vector<int> reqs;
	int due = 0;
};
vector<day> days;
int N;
bool check(int num) {
	int jobs = 0, done = 0;
	for (int i = 1; i <= N; i++) {
		jobs = max(0, jobs + static_cast<int>(days[i].reqs.size()) - num);
		done += num - days[i].due;
		if (done < 0)
			return false;
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int D, M;
	cin >> N >> D >> M;
	days.resize(N+1);
	for (int i = 1; i <= M; i++) {
		int req;
		cin >> req;
		days[req].reqs.push_back(i);
		days[req + D].due++;	
	}
	int l = 1, r = 1e+6;
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	cout << l << '\n';
	// queue<int> jobs;
	// for (int i = 1; i <= N; i++) {
	// 	for (const auto& i : days[i].reqs)
	// 		jobs.push(i);
	// 	for (int i = 0; i < l && !jobs.empty(); i++) {
	// 		cout << jobs.front() << ' ';
	// 		jobs.pop();
	// 	}
	// 	cout << "0\n";
	// }
}

• Subtask 1: 0 / 100