Intermediate.
Put your skills to the test.

Problem summary

Choose positive integers b1,…,bN to minimize Σ ai·bi, subject to every distinct value occurring at most K times among the b values. Answer Q independent queries with different K.

Constraints

1 ≤ N ≤ 500000; 1 ≤ Q ≤ 750000; 1 ≤ ai ≤ 1000000; 1 ≤ K ≤ 10^9.

Worked example

Original statement sample.

8 9
40 100 77 15 44 22 47 38
7 5 3 8 4 2 1 6 9

398 458 579 383 498 741 1273 420 383

Solution analysis

1. Since all ai are positive, use the smallest available b values: K copies of 1, then K copies of 2, and so on, with a possibly incomplete final block. Sort ai in decreasing order and pair the largest coefficients with the smallest multipliers.
2. Why this pairing? If a≥a′ and b≤b′, assigning (a,b),(a′,b′) instead of (a,b′),(a′,b) reduces the sum by (a−a′)(b′−b), which is nonnegative. Thus the optimal multiplier for sorted zero-based position i is floor(i/K)+1.
3. Build prefix sums of the sorted coefficients. For a fixed K, obtain each block sum in O(1) and multiply by its block number. Precompute answers for all 1≤K≤N. The total number of blocks over all K is O(N log N), so even many queries are cheap. When K≥N all multipliers are 1 and the answer is the total sum.
4. In the sample the total ai sum is 383. For K=7 only the smallest coefficient, 15, needs multiplier 2, adding 15 to give 398. For K=8 or 9 every coefficient receives multiplier 1, giving 383.

Why it works

Any skipped smaller multiplier can replace a larger one without violating the frequency cap and strictly improve the sum. Therefore the optimal multiplier multiset is the smallest allowed one. The exchange inequality proves that opposite sorted order is optimal; the prefix-sum block computation evaluates exactly this assignment.

Watch out. Do not compute O(N) work for every query. Clamp K to N before looking up the answer. Use long long for prefix sums and products: the maximum sum can be around 1.25×10^17.

An independently written complete program with standard headers.

#include<algorithm>
#include<functional>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,queries;
    cin>>n>>queries;
    vector<int>values(n);
    for(int&value:values){
        cin>>value;
    }
    sort(values.begin(),values.end(),greater<int>());
    vector<long long>prefix(n+1,0),answer(n+1,0);
    for(int index=0;index<n;index++){
        prefix[index+1]=prefix[index]+values[index];
    }
    for(int capacity=1;capacity<=n;capacity++){
        long long multiplier=1;
        for(int left=0;left<n;left+=capacity){
            int right=min(n,left+capacity);
            // A whole block receives the same smallest unused multiplier.
            answer[capacity]+=(prefix[right]-prefix[left])*multiplier;
            multiplier++;
        }
    }
    for(int query=0;query<queries;query++){
        long long capacity;
        cin>>capacity;
        if(query>0){
            cout<<' ';
        }
        cout<<answer[static_cast<int>(min(capacity,1LL*n))];
    }
    cout<<'\n';
}