Submission #1277627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277627		random_name	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	148 ms	11676 KiB

jobs

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

int main(){
	ll n,d,m; cin>>n>>d>>m;
	vector<vector<ll>> J(n);
	for(ll i=0;i<m;i++){
		ll a;cin>>a;
		J[a-1].push_back(i);
	}

	ll l=1,r=m;
	while(l<r){
		ll mid=(l+r)/2;
		bool able=true;
		queue<pair<ll, ll>> q;
		for(ll i=0;i<n;i++){
			q.push({i, J[i].size()});

			if(q.front().first + d < i){
				able = false;
				break;
			}
			
			ll diff = mid;
			while(!q.empty() && diff > 0){
				if(q.front().second <= diff){
					diff -= q.front().second;
					q.pop();
				}

				else{
					q.front().second -= diff;
					diff = 0;
				}
			}
		}

		if(q.size() != 0){
			able = false;
		}

		if(able){
			r = mid;
		}

		else
			l = mid+1;
	}

	cout << l << '\n';

	// queue<pair<ll, ll>> q;
	// for(ll i=0;i<n;i++){
	// 	q.push({i, J[i].size()});
		
	// 	ll diff = l;
	// 	while(!q.empty() && diff > 0){
	// 		if(q.front().second <= diff){
	// 			diff -= q.front().second;
	// 			for(ll j=0;j<q.front().second;j++){
	// 				cout << J[q.front().first].back()+1 << ' ';
	// 				J[q.front().first].pop_back();
	// 			}
	// 			q.pop();
	// 		}

	// 		else{
	// 			for(ll j=0;j<diff;j++){
	// 				cout << J[q.front().first].back()+1 << ' ';
	// 				J[q.front().first].pop_back();
	// 			}

	// 			q.front().second -= diff;
	// 			diff = 0;
	// 		}
	// 	}

	// 	cout << 0 << '\n';
	// }
}

• Subtask 1: 0 / 100