| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 305202 | updown1 | Job Scheduling (CEOI12_jobs) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int,int> pi;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define f first
#define s second
ll N, D, M;
bool check(vector<ll> x, int m) {
vector<ll> machT(m);
F0R(i, M) {
machT[i % m] = max(machT[i % m] + 1, x[i]);
if (machT[i % m] > x[i] + D) {
return false;
}
}
return true;
}
ll binary_search(vector<ll> x) {
ll r = N;
ll l = 1;
while (l != r) {
int mid = (l + r)/2;
if (check(x, mid)) {
r = mid;
}
else {
l = mid + 1;
}
}
return l;
}
int main() {
cin >> N >> D >> M;
vector<ll> jobs(M);
vector<pair<ll, int>> jp(M);
F0R(i, M) {
cin >> jobs[i];
jp[i] = {jobs[i], i};
}
sort(all(jobs));
sort(all(jp), [](pl a, pl b) {if (a.f == b.f) {return a.s > b.s;}
return a.f < b.f;});
ll machines = binary_search(jobs);
cout << machines << endl;
/*vector<vector<int>> sim(N + 1);
vector<ll> machT(machines);
F0R(i, M) {
machT[i % machines] = max(machT[i % machines] + 1, jobs[i]);
sim[machT[i % machines]].pb(jp[i].s + 1);
}
FOR(i, 1, N + 1) {
F0R(j, sim[i].size()) {
cout << sim[i][j] << " ";
}
cout << 0 << endl;
}*/
}