Submission #1270342

#TimeUsernameProblemLanguageResultExecution timeMemory
1270342xqyspJob Scheduling (CEOI12_jobs)C++17
0 / 100
184 ms3936 KiB
// https://oj.uz/problem/view/CEOI12_jobs

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

int main() {
    int N, D, M;
    cin >> N >> D >> M;
    vector<int> requests;
    requests.resize(M);
    for (int i = 0; i < M; i++) {
        cin >> requests[i];
    }
    sort(requests.begin(), requests.end());
    int left = 1, right = M;
    while (left < right) {
        int mid = (left + right) / 2;
        // cout<<mid<<endl;
        // 1 2 4 2 1 3 5 6 2 3 6 4
        // 1,1,2,2,2,3,3,4,4,5,6,6
        int index = 0;
        bool enough = true;
        for (int i = 1; i <= N; i++) {
            if (index >= M) {
                break;
            }
            for (int j = 0; j < mid; j++) {
                if (index >= M) {
                    break;
                }
                if (requests[index] > i + D) {
                    enough = false;
                    break;
                }
                if (requests[index] > i) {
                    break;
                }
                index++;
            }
            if (enough == false) {
                break;
            }
        }
        if(index<M-1){
            enough=false;
        }
        if (enough == true) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    cout << left;

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