Submission #1084308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084308		4QT0R	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	60 ms	14160 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

int zle[100003];
int wej[1000003];
vector<int> ans[100003];

deque<pair<int,int>> dq;
queue<int> q;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n,d,m;
	cin >> n >> d >> m;
	for (int i = 1; i<=m; i++){
		cin >> wej[i];
		zle[wej[i]]++;
		ans[wej[i]].push_back(i);
	}
	int l=1,p=m,md;
	while(l<p){
		md=(l+p)/2;
		bool ok=true;
		for (int i = 1; i<=n; i++){
			dq.push_back({zle[i],i});
			int lft=md;
			while(dq.size() && lft){
				auto [z,ind] = dq.front();
				dq.pop_front();
				if (lft>=z){
					lft-=z;
					z=0;
				}
				else{
					z-=lft;
					lft=0;
					dq.push_front({z,ind});
				}
			}
			if (dq.size() && dq.front().second+d<=i){
				ok=false;
				dq.clear();
				break;
			}
		}
		if (dq.size())ok=false;
		dq.clear();
		if (ok)p=md;
		else l=md+1;
	}
	cout << l << '\n';
	// for (int i = 1; i<=n; i++){
	// 	for (auto u : ans[i])q.push(u);
	// 	for (int j = 1; j<=l; j++){
	// 		if (q.empty())break;
	// 		cout << q.front() << ' ';
	// 		q.pop();
	// 	}
	// 	cout << "0\n";
	// }
}

• Subtask 1: 0 / 100