Submission #283542

#	Time	Username	Problem	Language	Result	Execution time	Memory
283542		ijxjdjd	Watching (JOI13_watching)	Java	100 / 100	515 ms	94208 KiB

watching

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.ArrayDeque;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class watching {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Watching solver = new Watching();
        solver.solve(1, in, out);
        out.close();
    }

    static class Watching {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int P = in.nextInt();
            int Q = in.nextInt();
            if (P >= N || Q >= N) {
                out.println(1);
            } else {
                int low = 1;
                int high = (int) (1e9);
                int[] A = new int[N];
                for (int i = 0; i < N; i++) {
                    A[i] = in.nextInt();
                }
                ArrayUtils.sort(A);
                while (low < high) {
                    int mid = (low + high) / 2;
                    int[] moveBig = new int[N];
                    int[] moveSmall = new int[N];
                    ArrayDeque<Integer> big = new ArrayDeque<>();
                    ArrayDeque<Integer> small = new ArrayDeque<>();
                    moveBig[N - 1] = N - 1;
                    moveSmall[N - 1] = N - 1;
                    big.add(A[N - 1]);
                    small.add(A[N - 1]);
                    for (int i = N - 2; i >= 0; i--) {
                        big.addFirst(A[i]);
                        small.addFirst(A[i]);
                        while (2 * mid + A[i] <= big.getLast()) {
                            big.removeLast();
                        }
                        while (mid + A[i] <= small.getLast()) {
                            small.removeLast();
                        }
                        moveBig[i] = i + big.size() - 1;
                        moveSmall[i] = i + small.size() - 1;
                    }
                    int[][] dp = new int[P + 1][Q + 1];
                    dp[0][0] = -1;
                    boolean flag = false;
                    cont:
                    for (int i = 0; i <= P; i++) {
                        for (int j = 0; j <= Q; j++) {
                            if (dp[i][j] == N - 1) {
                                flag = true;
                                break cont;
                            }
                            if (j + 1 <= Q) {
                                dp[i][j + 1] = Math.max(moveBig[dp[i][j] + 1], dp[i][j + 1]);
                            }
                            if (i + 1 <= P) {
                                dp[i + 1][j] = Math.max(moveSmall[dp[i][j] + 1], dp[i + 1][j]);
                            }
                        }
                    }
                    if (flag) {
                        high = mid;
                    } else {
                        low = mid + 1;
                    }
                }
                out.println(high);
            }
        }

    }

    static class ArrayUtils {
        public static void shuffle(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                int rand = (int) (Math.random() * (i + 1));
                swap(arr, i, rand);
            }
        }

        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        public static void sort(int[] arr) {
            shuffle(arr);
            Arrays.sort(arr);
            //get rid of quicksort cases
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50