Submission #636939

#	Time	Username	Problem	Language	Result	Execution time	Memory
636939		Omar_Elgedawy	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	192 ms	18576 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define F first
#define S second
#define el endl
#define cout(x) for(auto v:x)cout<<v<<' '
#define cin(x) for(auto &v:x)cin>>v;
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
int freq1[10001],freq2[10001];
void testcases(int h){
  int n,m,d;cin>>n>>d>>m;
  vector<int>v;
  for(int i=0;i<m;i++){
    int x;cin>>x;
    freq1[x]++;
    freq2[x]++;
    v.push_back(x);
  }
  int l=1,r=1e5,ans;
  while(l<=r){
    int m=(l+r)/2;
    int num=1,f=1;
    for(int i=1;i<=n;i++){
      int cur=m;
      if(i>num+d){
        f=0;
        break;
      }
      while(cur && freq1[num]<=cur && num<=i){
        cur-=freq1[num];
        freq1[num]=0;
        num++;
      }
      if(cur && num<=i){
        freq1[num]=freq1[num]-cur;
        cur=0;
      }
    }
    if(f){
      ans=m;
      r=m-1;
    }
    else{
      l=m+1;
    }
    for(int i=1;i<=n;i++){
      freq1[i]=freq2[i];
    }
  }
  cout<<ans<<el;
}
int32_t main()
{
  int tc=1;
  // cin>>tc;
  for(int i=1;i<=tc;i++)testcases(i);
  return 0;
}

• Subtask 1: 0 / 100