fork download
copy 
  1. def solve():
  2.     import sys
  3.     input = sys.stdin.read
  4.     data = input().split()
  5.  
  6.     t = int(data[0])
  7.     idx = 1
  8.     results = []
  9.  
  10.     for _ in range(t):
  11.         n, k = map(int, data[idx:idx + 2])
  12.         idx += 2
  13.         costs = list(map(int, data[idx:idx + n]))
  14.         idx += n
  15.  
  16.         # Sort the costs
  17.         costs.sort()
  18.  
  19.         # Prefix sums for the sorted costs
  20.         prefix_sum = [0] * (n + 1)
  21.         for i in range(1, n + 1):
  22.             prefix_sum[i] = prefix_sum[i - 1] + costs[i - 1]
  23.  
  24.         # Calculate minimum cost for buying m items
  25.         result = []
  26.         for m in range(1, n + 1):
  27.             # Calculate the number of items you need to pay for
  28.             free_items = (m - 1) // (k + 1)
  29.             paid_items = m - free_items
  30.             result.append(prefix_sum[paid_items])
  31.  
  32.         results.append(" ".join(map(str, result)))
  33.  
  34.     # Print all results
  35.     sys.stdout.write("\n".join(results) + "\n")
  36.  
Success #stdin #stdout 0.01s 7196KB
comments (?)
stdin
copy 
2
 5 1
 4 1 6 10 2
 3 2
 1 1 1
stdout
copy 
Standard output is empty
https://ideone.com/KVUAVu
language:
Python (cpython 2.7.16)
created:
6 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!