fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.  
  7.         int T = sc.nextInt();
  8.  
  9.         while (T-- > 0) {
  10.             int N = sc.nextInt();
  11.             int K = sc.nextInt();
  12.  
  13.             long[] A = new long[N];
  14.             long[] C = new long[N];
  15.  
  16.             HashSet<Long> values = new HashSet<>();
  17.  
  18.             for (int i = 0; i < N; i++) {
  19.                 A[i] = sc.nextLong();
  20.                 values.add(A[i]);
  21.             }
  22.  
  23.             for (int i = 0; i < N; i++)
  24.                 C[i] = sc.nextLong();
  25.  
  26.             long ans = 0;
  27.  
  28.             for (long x : values) {
  29.  
  30.                 int greater = 0;
  31.                 int equal = 0;
  32.  
  33.                 ArrayList<Long> costs = new ArrayList<>();
  34.  
  35.                 for (int i = 0; i < N; i++) {
  36.  
  37.                     if (A[i] > x)
  38.                         greater++;
  39.  
  40.                     else if (A[i] == x)
  41.                         equal++;
  42.  
  43.                     else
  44.                         costs.add((x - A[i]) * C[i]);
  45.                 }
  46.  
  47.                 if (greater > K)
  48.                     continue;
  49.  
  50.                 int need = K + 1 - (greater + equal);
  51.  
  52.                 if (need < 0)
  53.                     need = 0;
  54.  
  55.                 if (need > costs.size())
  56.                     continue;
  57.  
  58.                 Collections.sort(costs);
  59.  
  60.                 long spend = 0;
  61.  
  62.                 for (int i = 0; i < need; i++)
  63.                     spend += costs.get(i);
  64.  
  65.                 long profit = 1L * K * x - spend;
  66.  
  67.                 ans = Math.max(ans, profit);
  68.             }
  69.  
  70.             System.out.println(ans);
  71.         }
  72.     }
  73. }
Success #stdin #stdout 0.11s 56440KB
comments (?)
stdin
copy 
3
3 1
6 1 9
4 5 1
4 2
6 11 2 1
4 1 1 3
5 3
1 2 3 4 5
1 2 3 4 5
stdout
copy 
6
8
7
https://ideone.com/JhhgNE
language:
Java (HotSpot 12)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!