oj.uz

Submission #283542

# Submission time Handle Problem Language Result Execution time Memory
283542 2020-08-25T23:32:51 Z ijxjdjd Watching (JOI13_watching) Java 11
100 / 100
 515 ms 94208 KB 
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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 10584 KB Output is correct
2 Correct 77 ms 10340 KB Output is correct
3 Correct 88 ms 10240 KB Output is correct
4 Correct 78 ms 10360 KB Output is correct
5 Correct 84 ms 10232 KB Output is correct
6 Correct 76 ms 10216 KB Output is correct
7 Correct 92 ms 10740 KB Output is correct
8 Correct 90 ms 10728 KB Output is correct
9 Correct 93 ms 10612 KB Output is correct
10 Correct 107 ms 10952 KB Output is correct
11 Correct 94 ms 10728 KB Output is correct
12 Correct 103 ms 10904 KB Output is correct
13 Correct 93 ms 10628 KB Output is correct
14 Correct 89 ms 10540 KB Output is correct
15 Correct 91 ms 10868 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 15152 KB Output is correct
2 Correct 76 ms 10304 KB Output is correct
3 Correct 433 ms 94208 KB Output is correct
4 Correct 78 ms 10104 KB Output is correct
5 Correct 84 ms 10596 KB Output is correct
6 Correct 84 ms 10360 KB Output is correct
7 Correct 172 ms 15148 KB Output is correct
8 Correct 245 ms 27924 KB Output is correct
9 Correct 241 ms 28568 KB Output is correct
10 Correct 269 ms 37904 KB Output is correct
11 Correct 234 ms 36484 KB Output is correct
12 Correct 515 ms 69968 KB Output is correct
13 Correct 169 ms 14840 KB Output is correct
14 Correct 188 ms 15108 KB Output is correct
15 Correct 176 ms 14832 KB Output is correct