Submission #260704

#TimeUsernameProblemLanguageResultExecution timeMemory
260704ijxjdjdJust Long Neckties (JOI20_ho_t1)Java
9 / 100
1339 ms60052 KiB
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();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...