Submission #1119564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1119564	2024-11-27T06:44:36 Z	johu	Job Scheduling (CEOI12_jobs)	Java 11	100 / 100	974 ms	29924 KB

jobs

import java.io.*;
import java.util.*;

public class jobs {
    private static final int MX = (int) 1e6 + 5;
    private static int N, M, D;
    private static int[] cnt = new int[MX];

    private static boolean f(int x) {
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if (!dq.isEmpty() && dq.peekFirst() < i) return false;
            for (int j = 0; j < cnt[i]; j++) dq.addLast(i + D);
            for (int j = 0; j < x; j++) {
                if (dq.isEmpty()) break;
                dq.pollFirst();
            }
        }
        return dq.isEmpty();
    }

    public static void main(String[] args) throws IOException {
        DataInputStream dis = new DataInputStream(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(dis));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        Arrays.fill(cnt, 0);
        for (int i = 0; i < M; i++) {
            int x = Integer.parseInt(st.nextToken());
            cnt[x]++;
        }

        int l = 1, r = M, ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (f(mid)) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }

        System.out.println(ans);
        for (int i = 0; i < N; i++) System.out.println(0);
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	522 ms	20368 KB	Output is correct
2	Correct	471 ms	20360 KB	Output is correct
3	Correct	462 ms	20052 KB	Output is correct
4	Correct	461 ms	20096 KB	Output is correct
5	Correct	454 ms	20228 KB	Output is correct
6	Correct	478 ms	20384 KB	Output is correct
7	Correct	497 ms	20372 KB	Output is correct
8	Correct	508 ms	20112 KB	Output is correct
9	Correct	879 ms	18376 KB	Output is correct
10	Correct	798 ms	18460 KB	Output is correct
11	Correct	273 ms	18256 KB	Output is correct
12	Correct	364 ms	20944 KB	Output is correct
13	Correct	334 ms	23520 KB	Output is correct
14	Correct	582 ms	26032 KB	Output is correct
15	Correct	433 ms	24796 KB	Output is correct
16	Correct	595 ms	28724 KB	Output is correct
17	Correct	591 ms	29596 KB	Output is correct
18	Correct	655 ms	29560 KB	Output is correct
19	Correct	974 ms	29856 KB	Output is correct
20	Correct	663 ms	29924 KB	Output is correct