제출 #619677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619677		gmsong	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	277 ms	8576 KiB

jobs

// Source: https://usaco.guide/general/io

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

int n, d, m;
vector<pair<int, int> > v;

vector<vector<int> > schedule(n);

bool possible(int machines){
	int i = 0;
	int curAmt = 0;
	int day = 1;
	while(i < m){
		curAmt++;
		// cout << "day is " << day << endl;
		// cout << "curAmt is " << curAmt << endl;
		// cout << "i is " << curAmt << endl;
		// cout << "v[i].first is " << v[i].first << endl;
		// cout << endl;
		if(v[i].first < day){
			return 0;
		}
		if(curAmt == machines){
			curAmt = 0;
			day++;
		}
		i++;
	}
	return 1;
}

int main() {
	cin >> n >> d >> m;

	
	for(int i = 1; i <= m; i++){
		int val;
		cin >> val;
		val += d;
		v.push_back({val, i});
	}
	sort(v.begin(), v.end());
	// cout << possible(11) << endl;
	int lo = 1;
	int hi = m + 10;
	int ans = 0;
	while(lo <= hi){
		int mid = (lo + hi)/2;
		// cout << "mid is " << mid << endl;
		if(possible(mid)){
			// cout << "worked" << endl;
			hi = mid - 1;
			ans = mid;
		}
		else{
			lo = mid + 1;
		}
	}
	// schedule[1 - 1].push_back(0);
	// int i = 0;
	// int curAmt = 0;
	// int day = 1;
	// vector<int> row;
	// while(i < m){
	// 	curAmt++;
		
	// 	// cout << "day is " << day << endl;
	// 	// cout << "curAmt is " << curAmt << endl;
	// 	// cout << "i is " << curAmt << endl;
	// 	// cout << "v[i].first is " << v[i].first << endl;
	// 	// cout << endl;
	// 	row.push_back(v[i].second);
	// 	if(curAmt == ans){
	// 		schedule.push_back(row);
	// 		row.clear();
	// 		curAmt = 0;
	// 		day++;
	// 	}
	// 	i++;
	// }
	// cout<< schedule[0].size() << endl;
	cout << ans << endl;
	// for(int i = 0; i < n; i++){
	// 	if(schedule[i].size() != 0){
	// 		for(int j = 0; j < schedule[i].size(); j++){
	// 			cout << schedule[i][j] << " ";
	// 		}
	// 	}
	// 	cout << 0 << endl;
	// }
}

• Subtask 1: 0 / 100