Submission #874467

#TimeUsernameProblemLanguageResultExecution timeMemory
874467vjudge1Job Scheduling (CEOI12_jobs)C++17
0 / 100
1096 ms52424 KiB
//In His Name
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
#define ceil(x,y) x/y + min(1ll,x%y)
const int maxn = 5e3 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

int n , d , m;
vector<int> v;
bool check(int mid){
    multiset<int> s;
    for(int i : v) s.insert(i);
    int cnt = 1;
    while(s.size()){
       for(int i = 1 ; i <= d ; i++){
           if(cnt - *s.begin() > d) return true;
           if(*s.begin() <= cnt) s.erase(s.begin());
           else break;
       }
       cnt++;
    }
    return false;
}

signed main(){
    ios_base::sync_with_stdio(false);

    cin >> n >> d >> m;
    for(int i = 1 ; i <= m ; i++){
        int x;
        cin >> x;
        v.pb(x);
    }
    int l = 1 , r = 1e9;
    while(r - l > 1){
        int mid = (l+r) >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << r;

}
#Verdict Execution timeMemoryGrader output
Fetching results...