fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve() {
  5.     int t;
  6.     cin >> t;
  7.     while (t--) {
  8.         int n, k;
  9.         cin >> n >> k;
  10.         vector<int> v(n);
  11.  
  12.         for (int i = 0; i < n; i++) {
  13.             cin >> v[i];
  14.         }
  15.  
  16.         // Sort the costs
  17.         sort(v.begin(), v.end());
  18.  
  19.         // Compute prefix sums
  20.         vector<long long> prefix(n + 1, 0);
  21.         for (int i = 1; i <= n; i++) {
  22.             prefix[i] = prefix[i - 1] + v[i - 1];
  23.         }
  24.  
  25.         // Calculate the minimum cost for each m
  26.         vector<long long> result(n);
  27.         for (int m = 1; m <= n; m++) {
  28.             int free_items = (m - 1) / (k + 1);
  29.             int paid_items = m - free_items;
  30.             result[m - 1] = prefix[paid_items];
  31.         }
  32.  
  33.         // Output the result for this test case
  34.         for (int i = 0; i < n; i++) {
  35.             cout << result[i] << " ";
  36.         }
  37.         cout << "\n";
  38.     }
  39. }
  40.  
  41. int main() {
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(nullptr);
  44.     solve();
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
2
 5 1
 4 1 6 10 2
 3 2
 1 1 1
stdout
copy 
1 3 3 7 7 
1 2 3
https://ideone.com/O11ZsI
language:
C++ (gcc 8.3)
created:
5 days 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!