fork download
copy 
  1. import java.util.*;
  2. class main {
  3.     public static void main(String[] args) {
  4.         Scanner scanner = new Scanner(System.in);
  5.         int t = scanner.nextInt(); 
  6.  
  7.         StringBuilder result = new StringBuilder();
  8.  
  9.         while (t-- > 0) {
  10.             int n = scanner.nextInt(); 
  11.             int k = scanner.nextInt(); 
  12.             int[] prices = new int[n];
  13.  
  14.             for (int i = 0; i < n; i++) {
  15.                 prices[i] = scanner.nextInt();
  16.             }
  17.  
  18.             Arrays.sort(prices);
  19.  
  20.             long[] prefixSum = new long[n + 1];
  21.             for (int i = 0; i < n; i++) {
  22.                 prefixSum[i + 1] = prefixSum[i] + prices[i];
  23.             }
  24.  
  25.             long[] minCost = new long[n + 1];
  26.             for (int m = 1; m <= n; m++) {
  27.                 minCost[m] = prefixSum[m];
  28.                 if (m > k) {
  29.                     minCost[m] = Math.min(minCost[m], minCost[m - k - 1] + prefixSum[m] - prefixSum[m - k]);
  30.                 }
  31.             }
  32.  
  33.             for (int m = 1; m <= n; m++) {
  34.                 result.append(minCost[m]).append(" ");
  35.             }
  36.             result.append("\n");
  37.         }
  38.  
  39.         System.out.println(result.toString());
  40.     }
  41. }
Success #stdin #stdout 0.17s 54560KB
comments (?)
stdin
copy 
2
5 2
4 1 6 10 2
3 2
1 1 1
stdout
copy 
1 3 6 11 19 
1 2 2
https://ideone.com/1HtOC4
language:
Java (HotSpot 12)
created:
1 day 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!