Submission

Score: 7

User: kungarooo

Problemset: แคง (Kang)

Language: cpp

Time: 2.093 second

Submitted On: 2025-08-02 23:07:31

#include <bits/stdc++.h>
using namespace std;
long long int sum=0;
unordered_map<long long int,long long int> c;
unordered_map<int,int> in;
// long long wdym(int d){

//     long long int sub=0;
//     for(int i=0;i<d&&!pq.empty();i++){
//         sub+=pq.top();
//         pq.pop();
//     }
//     return sum-sub;
// }
std::vector<long long> capsize(std::vector<int> A, std::vector<int> B){
    int m=B.size();
    
    sort(A.begin(),A.end());
    vector<int> BB=B;
    sort(BB.begin(),BB.end());
    for(int i=0;i<A.size();){
        int idx=i;
        while(++i<A.size()&&A[i]==A[idx]){}
        c[A[idx]]=A[idx]*((long long int)(i-idx));
        sum+=A[idx]*((long long int)(i-idx));
    }
    for(int i=0;i<BB.size();){
        int idx=i;
        while(++i<BB.size()&&BB[i]==BB[idx]){}
        c[BB[idx]]+=BB[idx]*((long long int)(i-idx));
        sum+=BB[idx]*((long long int)(i-idx));
    }

    priority_queue<pair<long long int,long long int>> pq;
    multiset<int> l;
    for(auto i:c){
        //l.insert(i.second);
        pq.push({i.second,i.first});
    }
    long long int sub=0;
    for(int j=0;j<m&&!pq.empty();j++){
        sub+=pq.top().first;
        l.insert(pq.top().first);
        //in[pq.top().second]=1;
        pq.pop();
    }
    // for(auto i:l){
    //     cout<<i<<" ";
    // }
    // cout<<"\n";
    vector<long long> ret;
    for(int i=m;i>=1;i--){
        ret.push_back(sum-sub);
        l.erase(c[B[i-1]]);
        c[B[i-1]]-=B[i-1];
        l.insert(c[B[i-1]]);
        sum-=B[i-1];
        sub-=B[i-1];
        sub-=*(l.begin());
        l.erase(*(l.begin()));
        //cout<<sum<<" "<<sub<<"\n";
    }
    reverse(ret.begin(),ret.end());
    return ret;
}
//     int32_t main(){
//     int n, m;
//     cin >> n >> m;
//     vector<int> A(n), B(m);
//     for(auto &x: A) cin >> x;
//     for(auto &x: B) cin >> x;
//     vector<long long> ans =  capsize(A,B);
//     for(auto x: ans){
//         cout << x <<" ";
//     }
// }
/*
5 4
6 3 9 6 3
4 6 9 6
*/