Submission #1119580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119580		johu	Job Scheduling (CEOI12_jobs)	Java	95 / 100	1047 ms	24172 KiB

jobs

import java.util.*;
import java.io.*;
public class jobs {
    static BufferedReader br = new BufferedReader(new InputStreamReader(new DataInputStream(System.in)));
    static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        int N = nextInt(), D = nextInt(), M = nextInt(), cnt[] = new int[N + 1];
        for (int i = 0; i < M; i++)
            cnt[nextInt()]++;
        int l = 1, r = M, ans = 0;
        while (l <= r) {
            int m = (l + r) >> 1;
            boolean b = true;
            Deque<Integer> dq = new ArrayDeque<>();
            for (int i = 1; i <= N; i++) {
                if (!dq.isEmpty() && dq.peekFirst() < i) {
                    b = false;
                    break;
                }
                for (int j = 0; j < cnt[i]; j++)
                    dq.addLast(i + D);
                for (int j = 0; j < m; j++) {
                    if (dq.isEmpty()) break;
                    dq.pollFirst();
                }
            }
            if (b) {
                r = m - 1;
                ans = m;
            }
            else
                l = m + 1;
        }
        System.out.println(ans);
        for (int i = 0; i < N; i++)
            System.out.println(0);
    }
    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
    static char nextChar() throws IOException {
        return next().charAt(0);
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
    static String nextLine() throws IOException {
        return br.readLine().trim();
    }
}

• Subtask 1: 95 / 100