Submission #716133

#	Time	Username	Problem	Language	Result	Execution time	Memory
716133		PVSekhar	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	177 ms	680 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000000007;
bool check(int x,vector<int>& v,int d,int n){
    bool c=true;
    int p_vac=0,p_day=0;
    // cout<<x<<endl;
    for (int i = 1; i <= n; i++)
    {
        // for (int i = 0; i < n; i++)
        // {
        //     cout<<p_day<<" ";
        // }
        if(!c)break;
        if(p_day==0&&v[i]==0)continue;
        if(p_day&&v[i]==0){
            p_day--;
            p_vac=0;
            continue;
        }
        if(p_day==0){
            p_day=(v[i]+x-1)/x;
            if(p_day>d){
                c=false;
                break;
            }
            p_day--;
            p_vac=x-v[i]%x;
            if(p_vac==x)p_vac=0;
            continue;
        }
        if(p_vac&&v[i]<=p_vac){
            p_vac--;
        }else{
            v[i]-=p_vac;
            p_day+=(v[i]+x-1)/x;
            if(p_day>d){
                c=false;
                break;
            }
            p_vac=x-v[i]%x;
            if(p_vac==x)p_vac=0;
        }
        p_day--;
    }
    // cout<<endl;
    return c;
}
int main()
{
    int n,d,m,x;
    cin>>n>>d>>m;
    vector<int> v(n+1,0);
    for (int i = 0; i < m; i++)
    {
        cin>>x;
        v[x]++;
    }
    int l=0,r=n,mid;
    while(r-l>1){
        mid=(l+r)/2;
        if(check(mid,v,d,n)){
            r=mid;
        }else{
            l=mid;
        }
    }
    cout<<r<<endl;
    return 0;
}

• Subtask 1: 0 / 100