Submission #143887

#	Time	Username	Problem	Language	Result	Execution time	Memory
143887		miguel	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	86 ms	384 KiB

jobs

/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define mp make_pair
const ll mod = 1000000007;
const ll nmax=1000003;
int n, d, m, cnt[100010];

bool check(int xd){
    multiset<pi> s;
    for(int i=1; i<=n; i++){
        int aval=xd;
        if(cnt[i]) s.insert({i, cnt[i]});
        //if(xd==2){dbg(i); for(pi j: s) cout<<j.x<<" "<<j.y<<endl;}
        if(s.size() && (*s.begin()).x<i-d) return 0;
        while(aval && s.size()){
            pi cur=*s.begin();
            if(aval>=cur.y){
                s.erase(s.begin());
                aval-=cur.y;
            }
            else{
                s.erase(s.begin());
                s.insert({cur.x, cur.y-aval});
                aval=0;
            }
        }
    }
    if(s.size()==0) return 1;
    else return 0;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>d>>m;
    for(int i=1, x; i<=m; i++){
        cin>>x;
        cnt[x]++;
    }
    //for(int i=1; i<=n; i++) cout<<cnt[i]<<" "; cout<<endl;
    int l=0, r=m;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<endl;
    cout<<0<<endl;
    return 0;
}

• Subtask 1: 0 / 100