oj.uz

답안 #283541

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
283541 2020-08-25T23:30:09 Z ijxjdjd 구경하기 (JOI13_watching) Java 11
50 / 100
 165 ms 15100 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 = 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -