Submission #52111

#	Time	Username	Problem	Language	Result	Execution time	Memory
52111		mra2322001	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	119 ms	34004 KiB

jobs

#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<(n); i++)
#define f1(i, n) for(int i=(1); i<=(n); i++)

using namespace std;
typedef long long ll;
const int N = 1000002;

int n, d, m, dd[N];
pair <int, int> a[N];

bool check(int x){
    f1(i, n) dd[i] = 0;
    bool ok = 1;
    for(int i = m; i >= 1; i--){
        ok = 0;
        for(int j = a[i].second; j >= a[i].first; j--){
            if(dd[j] < x){
                dd[j]++;
                ok = 1;
                break;
            }
        }
        if(!ok) return 0;
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
   
    cin >> n >> d >> m;
    f1(i, m){
        int x; cin >> x;
        a[i] = make_pair(i, i + d - 1);
    }
    int l = 0, r = m;
    sort(a + 1, a + n + 1, [&](pair <int, int> a1, pair <int, int> a2){
         if(a1.second != a2.second) return a1.second < a2.second;
         return a1.first < a2.first;
    });

    int ans = m;
    while(l <= r){
        int mid = (l + r)/2;
        if(check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans;
}

• Subtask 1: 0 / 100