Submission #933093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
933093	2024-02-25T03:05:01 Z	agg	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	168 ms	7888 KB

jobs

#include <stdio.h>
#include <iostream>
#include <deque>

using namespace std;

typedef long long ll;

int main() {
    int N, M, D;
    int cnt[1000000];
    cin >> N >> D >> M;

    for (int i = 0; i < M; i++) {
        int x;
        cin >> x;
        cnt[x]++; // budget counter
    }

    int l = 1, r = M, ans = 0;
    while (l <= r) { // bin search
        int mid = (l + r) >> 1;
        deque<int> dq;
        for (int i = 1; i <= N; i++) {
            if (dq.size() && dq.front() < i)
                break;
            for (int j = 0; j < cnt[i]; j++) // put in the jobs
                dq.push_back(i + D);
            for (int j = 0; j < mid; j++) {
                if (dq.empty())
                    break;
                dq.pop_front(); // remove allocated items up to mid
            }
        }

        if (dq.empty()) { // if no options then change downward
            r = mid - 1;
            ans = mid;
        } else { // go upward
            l = mid + 1;
        }
    }

    cout << ans << '\n';
    for (int i = 0; i < N; i++)
        cout << 0 << '\n';

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	5016 KB	Output is correct
2	Correct	20 ms	5084 KB	Output is correct
3	Correct	19 ms	5048 KB	Output is correct
4	Correct	19 ms	4956 KB	Output is correct
5	Correct	19 ms	5084 KB	Output is correct
6	Correct	20 ms	5036 KB	Output is correct
7	Correct	25 ms	5024 KB	Output is correct
8	Correct	24 ms	5200 KB	Output is correct
9	Correct	27 ms	4700 KB	Output is correct
10	Correct	26 ms	4696 KB	Output is correct
11	Correct	19 ms	4696 KB	Output is correct
12	Correct	37 ms	4964 KB	Output is correct
13	Correct	54 ms	5452 KB	Output is correct
14	Correct	103 ms	6220 KB	Output is correct
15	Correct	86 ms	6224 KB	Output is correct
16	Correct	121 ms	7116 KB	Output is correct
17	Correct	143 ms	7500 KB	Output is correct
18	Correct	142 ms	7376 KB	Output is correct
19	Correct	168 ms	7888 KB	Output is correct
20	Correct	146 ms	7520 KB	Output is correct