Submission #531239

#	Time	Username	Problem	Language	Result	Execution time	Memory
531239		Stormersyle	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	340 ms	9128 KiB

jobs

#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";
}

• Subtask 1: 0 / 100