Submission #934394

#	Time	Username	Problem	Language	Result	Execution time	Memory
934394		tamir1	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	225 ms	18256 KiB

jobs

#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
using namespace std;
ll i,n,d,m,l,r,mid;
pair<ll,ll> a[1000005];
bool check(ll mid){
	ll i,j,day=0;
	for(i=1;i<=m;){
		day++;
		for(j=i;j<i+mid && j<=m;j++){
			if(a[j].ff<day) break;
			if(day>a[j].ff+d) return 0;
		}
		i=j+1;
	}
	if(day>n) return 0;
	return 1;
}
int main(){
	cin >> n >> d >> m;
	for(i=1;i<=m;i++){
		cin >> a[i].ff;
		a[i].ss=i;
	}
	sort(a+1,a+m+1);
	l=1;
	r=m;
	while(r-l>1){
		mid=(r+l+1)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	if(check(l)) cout << l;
	else cout << r;
}

• Subtask 1: 0 / 100