Submission

Score: 100

User: mydKN

Problemset: แคง (Kang)

Language: cpp

Time: 1.852 second

Submitted On: 2025-06-30 14:25:12

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define emp emplace_back
#define em emplace
#define pb push_back

struct stc{
    ll val, cnt;
    bool operator<(const stc &o) const{
        return val*cnt < o.val * o.cnt;
    }
};

unordered_map<ll, ll> mp;
unordered_map<ll, bool> found;
priority_queue<stc> pq;
vector<ll> res;
ll sum;

vector<ll> capsize(vector<int> A, vector<int> B){
    res.reserve((int)B.size());
    mp.reserve((int)(A.size()+B.size()));
    found.reserve((int)(A.size()+B.size()));
    for(auto e : A){
        ++mp[e];
    }
    for(auto [e, x] : mp){
        pq.push({e, x});
        sum += e * x;
    }
    // cout << sum << "\n";
    for(auto e : B){
        if(!found[e]){
            sum += e;
            int tmp = ++mp[e];
            pq.push({e, tmp});
        }
        while(!pq.empty() && (found[pq.top().val] || pq.top().cnt != mp[pq.top().val])){
            pq.pop();
        }
        if(!pq.empty()){
            found[pq.top().val] = 1;
            sum -= (pq.top().val * pq.top().cnt);
            pq.pop();
        }
        res.emp(max(0ll, sum));
    }
    while(res.size() < B.size()) res.emp(0ll);
    return res;
}
/*
int main() {
	int n, m;
	vector<int> A, B;
	cin >> n >> m;
	A.resize(n);
	B.resize(m);
	for(auto &e : A) cin >> e;
	for(auto &e : B) cin >> e;
	vector<ll> vec = capsize(A, B);
	for(auto e : vec) cout << e << " ";
}
*/