Submission #260712

#	Time	Username	Problem	Language	Result	Execution time	Memory
260712		ijxjdjd	Just Long Neckties (JOI20_ho_t1)	Java	100 / 100	919 ms	71712 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];
        int[] B = new int[N];
        st = new StringTokenizer(in.readLine());
        for (int i = 0; i <= N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        int[] sortB = radixSort(B.clone());
        int[] sortA = radixSort(A.clone());
        int[] prefMax = new int[N];
        prefMax[0] = A[sortA[0]] - B[sortB[0]];
        for (int i = 1; i < N; i++) {
            prefMax[i] = Math.max(prefMax[i-1], A[sortA[i]] - B[sortB[i]]);
        }
        int suffixMax = 0;
        int[] ans = new int[N+1];
        for (int i = N; i >= 1; i--) {
            ans[sortA[i]] = Math.max(0, Math.max(suffixMax, prefMax[i-1]));
            suffixMax = Math.max(A[sortA[i]] - B[sortB[i-1]], suffixMax);
        }
        ans[sortA[0]] = Math.max(0, suffixMax);
        for (int i : ans) {
            out.print(i + " ");
        }
        out.close();
    }
    static int[] radixSort(int[] key) {
        int[] sort = new int[key.length];
        for (int i = 0; i < key.length; i++) {
            sort[i] = i;
        }
        int max = 1;
        while (max > 0) {
            int[] next = new int[sort.length];
            int[] bucket = new int[10];
            max = 0;
            for (int i = 0; i < key.length; i++) {
                bucket[key[i]%10]++;
            }
            for (int i = 1; i < 10; i++) {
                bucket[i] += bucket[i-1];
            }
            for (int i = sort.length-1; i >= 0; i--) {
                next[--bucket[key[sort[i]]%10]] = sort[i];
                key[sort[i]]/=10;
                max = Math.max(key[sort[i]], max);
            }
            sort = next.clone();
        }
        return sort;
    }
}

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