Submission #1269707

#TimeUsernameProblemLanguageResultExecution timeMemory
1269707WH8Job Scheduling (CEOI12_jobs)C++20
0 / 100
165 ms13224 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'

signed main(){
	int n,d,m;cin>>n>>d>>m;
	vector<vector<int>> v(n+1);
	for(int i=1;i<=m;i++){
		int d;cin>>d;
		v[d].pb(i);
	}
	int l=0, r=1000000,mac;
	while(r-l>1){
		mac=(l+r)/2;
		vector<int> use(n+1, 0), rem(n+1,0);
		for(int i=1;i<=n;i++)rem[i]=v[i].size();
		int usep=0;
		bool ok=true;
		for(int i=1;i<=n;i++){
			usep=max(usep, i);
			while(rem[i] and usep<=i+d){
				int take=min(rem[i], mac-use[usep]);
				use[usep]+=take;
				rem[i]-=take;
				if(use[usep]==mac)usep++;
			}
			if(rem[i] and usep > i+d){
				ok=false;
				break;
			}
		}
		//~ printf("with %lld machines, use is \n", mac);
		//~ for(int i=1;i<=n;i++){
			//~ cout<<use[i]<<" ";
		//~ }
		//~ cout<<endl;
		if(ok){
			r=mac;
		}
		else l=mac;
	}
	cout<<r<<"\n";
	//~ vector<vector<int>> ans(n+1);
	//~ int usep=
	//~ for(int i=1;i<=n;i++){
		//~ while(v[i].size() >= 0){
			//~ ans[
			
}
#Verdict Execution timeMemoryGrader output
Fetching results...