제출 #84453

#제출 시각아이디문제언어결과실행 시간메모리
84453someone_aaJob Scheduling (CEOI12_jobs)C++17
0 / 100
1085 ms33792 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
multiset<int>tasks;
int n, d, m;

bool check(int x) {
    multiset<int> curr = tasks;
    for(int i=1;i<=n;i++) {
        //cout<<i<<": \n";
        for(int j=0;j<x && curr.size();j++) {
            auto it = curr.lower_bound(i-d);
            //cout<<"Found: "<<(*it)<<"\n";
            if(curr.size() == 0 && it == curr.end()) break;
            if(*it > i) break;
            else curr.erase(it);
        }
    }
    return curr.size() == 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>d>>m;
    int x;
    for(int i=1;i<=m;i++) {
        cin>>x;
        tasks.insert(x);
    }

    int index = m;
    for(int cekor = m/2;cekor>0;cekor/=2) {
        while(index-cekor>=0 && check(index-cekor)) index-=cekor;
    }
    cout<<index<<"\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...