Submission

Score: 15

User: foldnut

Problemset: แคง (Kang)

Language: cpp

Time: 1.623 second

Submitted On: 2026-03-31 21:11:25

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<ll> capsize(vector<int> a, vector<int> b){
  int n = a.size(), m = b.size();
  vector<ll> ans(m);
  priority_queue<pair<ll, ll>> pq;
  unordered_map<ll, ll> fq;
  ll sm = 0, r = 0;
  for(int i = 0;i<n;i++) fq[a[i]]++;
  for(auto [x, y] : fq){
    pq.push({x * y, x});
    sm += x * y;
  }
  unordered_set<int> in;
  for(int i = 0;i<m;i++){
    sm += b[i];
    if(in.count(b[i])){
      r += b[i];
      if(!pq.empty()){
        r += pq.top().first;
        in.insert(pq.top().second);
        pq.pop();
      }
    }else{
      pq.push({(fq[b[i]]++ + 1) * b[i], b[i]});
      while(!pq.empty()){
        if(!in.count(pq.top().second)) break;
        pq.pop();
      }
      if(!pq.empty()){
        r += pq.top().first;
        in.insert(pq.top().second);
        pq.pop();
      }
    }
    ans[i] = sm - r;
  }
  return ans;
}