제출 #631547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631547		andrei_boaca	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	307 ms	16808 KiB

jobs

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

• Subtask 1: 0 / 100