oj.uz

답안 #933093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933093 2024-02-25T03:05:01 Z agg Job Scheduling (CEOI12_jobs) C++17
100 / 100
 168 ms 7888 KB 
#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

# 결과 실행 시간 메모리 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