Advertisement
Guest User

Untitled

a guest
Nov 18th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.02 KB | None | 0 0
  1. import mooc.*;
  2. import java.util.Arrays;
  3. import java.util.ArrayList;
  4. import java.util.ArrayDeque;
  5. import java.lang.Math;
  6.  
  7. class RadixSort {
  8.     static int digit(int x, int k) {
  9.         for (int i = 1; i <= k - 1; i++) {
  10.             x /= 10;
  11.         }
  12.         return x % 10;
  13.     }
  14.  
  15.     static ArrayList<Integer> sort(ArrayList<Integer> lst) {
  16.         int c[] = new int[10];
  17.  
  18.         for (int i = 0; i <= 9; i++) {
  19.             ArrayList<Integer> b = new ArrayList<Integer>();
  20.  
  21.             for (int j = 0; j <= 9; j++) {
  22.                 c[j] = 0;
  23.             }
  24.  
  25.             for (int j = 0; j < lst.size(); j++) {
  26.                 int num = lst.get(j);
  27.                 int d = digit(num, i);
  28.                 c[d] += 1;
  29.                 b.add(0);
  30.             }
  31.  
  32.             for (int j = 1; j <= 9; j++) {
  33.                 c[j] += c[j - 1];
  34.             }
  35.  
  36.             for (int j = lst.size() - 1; j >= 0; j--) {
  37.                 int d = digit(lst.get(j), i);
  38.                 b.set(c[d] - 1, lst.get(j));
  39.                 c[d] -= 1;
  40.             }
  41.  
  42.             lst = b;
  43.         }
  44.        
  45.         return lst;
  46.     }
  47. }
  48.  
  49. class Index {
  50.     public static void main(String args[]) {
  51.         try (EdxIO io = EdxIO.create()) {
  52.             int n, m;
  53.             int a[] = new int[6010];
  54.             int b[] = new int[6010];
  55.             long ans = 0;
  56.             ArrayList<Integer> lst = new ArrayList<Integer>();
  57.  
  58.             n = io.nextInt();
  59.             m = io.nextInt();
  60.  
  61.             for (int i = 0; i < n; i++) {
  62.                 a[i] = io.nextInt();
  63.             }
  64.             for (int i = 0; i < m; i++) {
  65.                 b[i] = io.nextInt();
  66.             }
  67.  
  68.             for (int i = 0; i < n; i++) {
  69.                 for (int j = 0; j < m; j++) {
  70.                     lst.add(a[i] * b[j]);
  71.                 }
  72.             }
  73.  
  74.             lst = RadixSort.sort(lst);
  75.  
  76.             for (int i = 0; i < n * m; i += 10) {
  77.                 ans += lst.get(i);
  78.             }
  79.  
  80.             io.print(ans);
  81.         }
  82.     }
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement