Submission #260704

#	Time	Username	Problem	Language	Result	Execution time	Memory
260704		ijxjdjd	Just Long Neckties (JOI20_ho_t1)	Java	9 / 100	1339 ms	60052 KiB

ho_t1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class ho_t1 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[][] A = new int[N+1][2];
        int[] B = new int[N];
        st = new StringTokenizer(in.readLine());
        for (int i = 0; i <= N; i++) {
            A[i][0] = Integer.parseInt(st.nextToken());
            A[i][1] = i;
        }
        st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(B);
        Arrays.sort(A, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] t1) {
                return Integer.compare(ints[0], t1[0]);
            }
        });
        int[] prefMax = new int[N];
        prefMax[0] = A[0][0] - B[0];
        for (int i = 1; i < N; i++) {
            prefMax[i] = Math.max(prefMax[i-1], A[i][0] - B[i]);
        }
        int suffixMax = 0;
        int[] ans = new int[N+1];
        for (int i = N; i >= 1; i--) {
            ans[A[i][1]] = Math.max(0, Math.max(suffixMax, prefMax[i-1]));
            suffixMax = Math.max(A[i][0] - B[i-1], suffixMax);
        }
        ans[A[0][1]] = Math.max(0, suffixMax);
        for (int i : ans) {
            out.print(i + " ");
        }
        out.close();
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 0 / 91