Submission #1201127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201127		shadowlord	Job Scheduling (CEOI12_jobs)	C++20	0 / 100	155 ms	1096 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long

bool possible(int d, int n,int mid, vector<int>&a)
{
    int i;
    for(i=0;i<a.size();i++)
    {
        if(a[i])
        {
            break;
        }
    }
    int sum=mid*(d+1);
    for(int j=i+d;j<a.size();j++)
    {
        if(a[j-d]>sum)
        {
            return false;
        }
        sum+=mid;
    }
    return true;
}


signed main()
{
    int n, d, m;
    cin >> n >> d >> m;
    map<int, int> mp;
    int maxi= -1;
    for (int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        if (x > maxi)
        {
            maxi = x;
        }
        mp[x]++;
    }
    cout << maxi << "\n";   
    vector<int>a(maxi+d+1,0);
    for(int i=1;i<a.size();i++)
    a[i]=mp[i];
    //print a
    // for(int i=0;i<a.size();i++)
    // {
    //     cout << a[i] << " ";
    // }
    // cout << "\n";
    for(int i=1;i<a.size();i++)
    {
        a[i]+=a[i-1];
    }
    // //print a
    // for(int i=0;i<a.size();i++)
    // {
    //     cout << a[i] << " ";
    // }
    // cout << "\n";
    int l=1;
    int r = INT_MAX;
    int ans = 0;
    while(l<=r)
    {
        int mid = (r - l) / 2 + l;
        if (!possible(d,n, mid, a))
        {
            l = mid + 1;
        }
        else
        {
            ans = mid;
            r = mid - 1;
        }
    }
    cout << ans << "\n";

    return 0;
}

• Subtask 1: 0 / 100