Submission #1358725

#TimeUsernameProblemLanguageResultExecution timeMemory
1358725jumpJob Scheduling (CEOI12_jobs)C++20
0 / 100
23 ms516 KiB
#include <bits/stdc++.h>
#define int long long
int n,d,m;
int jobs[100010];
bool solve(int amt){
  std::queue<std::pair<int,int>> q;
  for(int i=1;i<=n;i++){
    //std::cout << amt << ' ' << i << '\n';
    if(jobs[i]!=0)
    q.push({i,jobs[i]});
    int left = amt;
    if(!q.empty()&&i-d>q.front().first)return false;
    while(!q.empty()&&q.front().second<=left)left-=q.front().second,q.pop();
    if(!q.empty()&&q.front().second>left)q.front().second-=left;
  }
  return true;
}
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> d >> m;
  for(int i=0;i<m;i++){
    int day;
    std::cin >> day;
    jobs[day]+=1;
  }
  int l=0,r=m;
  while(l<r){
    int mid = (l+r)/2;
    if(solve(mid)){
      r=mid;
    }
    else{
      l=mid+1;
    }
  }
  std::cout << r;
}
#Result Execution timeMemoryGrader output
Fetching results...