Submission #390183

#	Time	Username	Problem	Language	Result	Execution time	Memory
390183		grobar	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	7 ms	548 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
int n,d,m;
int a[10001];
vector< pair<int,int> >par;
bool works(int x)
{
    int curr=0;
    for(int day=0;day<n;day++)
    {
        for(int j=0;j<x;j++)
        {
            if(curr<m && par[curr].first<=day+1 && par[curr].first>=day+1-d)
            {
                curr++;
            }else
            {
                break;
            }
        }
    }
    if(curr==m)
    {
        return true;
    }else
    {
        return false;
    }
}
int main()
{
    cin>>n>>d>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a[i];
        par.push_back(make_pair(a[i],i+1));
    }
    sort(par.begin(),par.end());
    int low=0,high=m,mid=0,ans=0;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(works(mid)==true)
        {
            ans=mid;
            high=mid-1;
        }else
        {
            low=mid+1;
        }
    }
    cout<<ans<<endl;
    /*
    int curr=0;
    for(int day=0;day<n;day++)
    {
        for(int j=0;j<ans;j++)
        {
            if(curr<m && par[curr].first<=day+1 && par[curr].first>=day+1-d)
            {
                cout<<par[curr].second<<" ";
                curr++;
            }else
            {
                break;
            }
        }
        cout<<0;
        cout<<endl;
    }
    */
}

• Subtask 1: 0 / 100