Submission #631547

#TimeUsernameProblemLanguageResultExecution timeMemory
631547andrei_boacaJob Scheduling (CEOI12_jobs)C++11
0 / 100
307 ms16808 KiB
#include <bits/stdc++.h>

using namespace std;
int n,m,d;
vector<int> sol[100005];
struct date
{
    int val,poz;
} v[1000005];
bool comp(date a, date b)
{
    return a.val<b.val;
}
bool ok(int nr)
{
    int poz=1;
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        sol[i].clear();
        while(poz<=m&&v[poz].val<=i&&cnt<nr)
        {
            cnt++;
            sol[i].push_back(v[poz].poz);
            if(i-v[poz].val>d)
                return 0;
            poz++;
        }
        sol[i].push_back(0);
    }
    if(poz>m)
        return 1;
    return 0;
}
int main()
{
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v[i].val;
        v[i].poz=i;
    }
    sort(v+1,v+m+1,comp);
    int st=1;
    int dr=m;
    int ans=m;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(ok(mij))
        {
            ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    cout<<ans<<'\n';
    /*bool z=ok(ans);
    for(int i=1;i<=n;i++,cout<<'\n')
        for(int j:sol[i])
            cout<<j<<' ';
    cout<<endl;*/
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...