oj.uz

Submission #260712

# Submission time Handle Problem Language Result Execution time Memory
260712 2020-08-10T18:57:00 Z ijxjdjd Just Long Neckties (JOI20_ho_t1) Java 11
100 / 100
 919 ms 71712 KB 
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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10404 KB Output is correct
2 Correct 80 ms 10256 KB Output is correct
3 Correct 86 ms 10184 KB Output is correct
4 Correct 91 ms 10212 KB Output is correct
5 Correct 83 ms 10304 KB Output is correct
6 Correct 84 ms 10012 KB Output is correct
7 Correct 81 ms 10216 KB Output is correct
8 Correct 86 ms 10360 KB Output is correct
9 Correct 76 ms 10212 KB Output is correct
10 Correct 77 ms 10304 KB Output is correct
11 Correct 76 ms 10232 KB Output is correct
12 Correct 80 ms 10232 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10404 KB Output is correct
2 Correct 80 ms 10256 KB Output is correct
3 Correct 86 ms 10184 KB Output is correct
4 Correct 91 ms 10212 KB Output is correct
5 Correct 83 ms 10304 KB Output is correct
6 Correct 84 ms 10012 KB Output is correct
7 Correct 81 ms 10216 KB Output is correct
8 Correct 86 ms 10360 KB Output is correct
9 Correct 76 ms 10212 KB Output is correct
10 Correct 77 ms 10304 KB Output is correct
11 Correct 76 ms 10232 KB Output is correct
12 Correct 80 ms 10232 KB Output is correct
13 Correct 89 ms 10512 KB Output is correct
14 Correct 113 ms 11104 KB Output is correct
15 Correct 126 ms 12316 KB Output is correct
16 Correct 83 ms 10344 KB Output is correct
17 Correct 128 ms 12680 KB Output is correct
18 Correct 128 ms 12232 KB Output is correct
19 Correct 142 ms 12340 KB Output is correct
20 Correct 130 ms 12392 KB Output is correct
21 Correct 130 ms 12432 KB Output is correct
22 Correct 133 ms 11872 KB Output is correct
23 Correct 159 ms 12388 KB Output is correct
24 Correct 138 ms 12600 KB Output is correct
25 Correct 142 ms 12776 KB Output is correct
26 Correct 138 ms 12788 KB Output is correct
27 Correct 147 ms 12764 KB Output is correct
28 Correct 140 ms 12192 KB Output is correct
29 Correct 130 ms 11768 KB Output is correct
30 Correct 140 ms 12316 KB Output is correct
31 Correct 144 ms 12596 KB Output is correct
32 Correct 145 ms 12492 KB Output is correct

Subtask #3
91.0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10404 KB Output is correct
2 Correct 80 ms 10256 KB Output is correct
3 Correct 86 ms 10184 KB Output is correct
4 Correct 91 ms 10212 KB Output is correct
5 Correct 83 ms 10304 KB Output is correct
6 Correct 84 ms 10012 KB Output is correct
7 Correct 81 ms 10216 KB Output is correct
8 Correct 86 ms 10360 KB Output is correct
9 Correct 76 ms 10212 KB Output is correct
10 Correct 77 ms 10304 KB Output is correct
11 Correct 76 ms 10232 KB Output is correct
12 Correct 80 ms 10232 KB Output is correct
13 Correct 89 ms 10512 KB Output is correct
14 Correct 113 ms 11104 KB Output is correct
15 Correct 126 ms 12316 KB Output is correct
16 Correct 83 ms 10344 KB Output is correct
17 Correct 128 ms 12680 KB Output is correct
18 Correct 128 ms 12232 KB Output is correct
19 Correct 142 ms 12340 KB Output is correct
20 Correct 130 ms 12392 KB Output is correct
21 Correct 130 ms 12432 KB Output is correct
22 Correct 133 ms 11872 KB Output is correct
23 Correct 159 ms 12388 KB Output is correct
24 Correct 138 ms 12600 KB Output is correct
25 Correct 142 ms 12776 KB Output is correct
26 Correct 138 ms 12788 KB Output is correct
27 Correct 147 ms 12764 KB Output is correct
28 Correct 140 ms 12192 KB Output is correct
29 Correct 130 ms 11768 KB Output is correct
30 Correct 140 ms 12316 KB Output is correct
31 Correct 144 ms 12596 KB Output is correct
32 Correct 145 ms 12492 KB Output is correct
33 Correct 850 ms 59688 KB Output is correct
34 Correct 811 ms 66448 KB Output is correct
35 Correct 837 ms 63516 KB Output is correct
36 Correct 880 ms 62220 KB Output is correct
37 Correct 919 ms 67380 KB Output is correct
38 Correct 850 ms 71712 KB Output is correct
39 Correct 866 ms 62380 KB Output is correct
40 Correct 863 ms 67312 KB Output is correct
41 Correct 840 ms 63344 KB Output is correct
42 Correct 908 ms 69884 KB Output is correct
43 Correct 824 ms 63500 KB Output is correct
44 Correct 839 ms 62104 KB Output is correct
45 Correct 898 ms 71316 KB Output is correct
46 Correct 879 ms 68144 KB Output is correct
47 Correct 817 ms 68540 KB Output is correct
48 Correct 790 ms 70608 KB Output is correct
49 Correct 795 ms 64012 KB Output is correct
50 Correct 865 ms 64588 KB Output is correct
51 Correct 890 ms 68904 KB Output is correct
52 Correct 853 ms 65160 KB Output is correct
53 Correct 904 ms 66432 KB Output is correct