# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
531239 | Stormersyle | Job Scheduling (CEOI12_jobs) | C++14 | 340 ms | 9128 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <bits/stdc++.h>
#include <array>
#include <fstream>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;
using ll=long long;
int N, D, M;
bool works(int k, int a[]){
int t=1; //currently working on jobs w/ deadline t
int b[N+1];
for (int i=0; i<=N; i++) b[i]=a[i];
for (int day=1; day<=N; day++){
int j=k; //j=jobs left for today
while (j>0){
if (j<b[t]) b[t]-=j, j=0;
else j-=b[t], b[t]=0, t++;
if (t>N) return true;
}
if (t<=day) return false;
// cout<<day<<" "<<t<<"\n";
}
return true;
}
int firstTrue(int lo, int hi, int a[]) {
hi++;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (works(mid, a)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
int main() {
cin>>N>>D>>M;
int a[N+1]; //a[d]=# of jobs with deadline d
for (int i=0; i<=N; i++) a[i]=0;
vector<pair<int, int>> v; //{deadline, request id}
for (int i=1; i<=M; i++){
int S;
cin>>S;
a[S+D]++;
v.push_back({S+D, i});
}
sort(v.begin(), v.end());
// for (int i=1; i<=N; i++) cout<<a[i]<<" ";
// cout<<works(2, a);
int k=firstTrue(1, 1000000, a);
cout<<k<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |