Submission

Score: 8

User: mydKN

Problemset: แคง (Kang)

Language: cpp

Time: 1.956 second

Submitted On: 2025-06-30 12:41:27

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")

using namespace std;

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

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

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(A.size()+B.size());
    found.reserve(A.size()+B.size());
    for(auto e : A){
        ++mp[e];
    }
    for(auto [e, x] : mp){
        ll tmp = e * x;
        pq.push({e, tmp});
        sum += tmp;
    }
    // cout << sum << "\n";
    for(auto e : B){
        // if(sum <= 0ll || pq.empty()) break;
        if(!found[e]){
            sum += e;
            int tmp = ++mp[e];
            pq.push({e, tmp * e});
        }
        while(!pq.empty()){
            ll curw = mp[pq.top().val] * pq.top().val;
            if(found[pq.top().val] || pq.top().w != curw) pq.pop();
            else break;
        }
        if(!pq.empty()){
            sum -= pq.top().w;
            found[pq.top().val] = 1;
            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 << " ";
}
*/