Submission #283541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283541	2020-08-25T23:30:09 Z	ijxjdjd	Watching (JOI13_watching)	Java 11	50 / 100	165 ms	15100 KB

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 = 0;
                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.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	10744 KB	Output is correct
2	Correct	77 ms	10568 KB	Output is correct
3	Correct	81 ms	10492 KB	Output is correct
4	Correct	78 ms	10228 KB	Output is correct
5	Correct	82 ms	10364 KB	Output is correct
6	Correct	83 ms	10336 KB	Output is correct
7	Correct	99 ms	11000 KB	Output is correct
8	Correct	101 ms	10808 KB	Output is correct
9	Correct	106 ms	10616 KB	Output is correct
10	Correct	104 ms	10772 KB	Output is correct
11	Correct	98 ms	10848 KB	Output is correct
12	Correct	111 ms	10804 KB	Output is correct
13	Correct	108 ms	10804 KB	Output is correct
14	Correct	99 ms	10856 KB	Output is correct
15	Correct	103 ms	10488 KB	Output is correct

Subtask #2

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	15100 KB	Output is correct
2	Runtime error	90 ms	10584 KB	Execution failed because the return code was nonzero
3	Halted	0 ms	0 KB	-