Submission

Score: 76

User: foldnut

Problemset: แคง (Kang)

Language: cpp

Time: 2.095 second

Submitted On: 2026-03-31 21:00:12

#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);
  set<pair<ll, ll>, greater<pair<ll, ll>>> s;
  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){
    s.insert({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(!s.empty()){
        r += s.begin()->first;
        in.insert(s.begin()->second);
        s.erase(s.begin());
      }
    }else{
      if(fq.count(b[i])){
        ll cc = fq[b[i]];
        s.erase({cc * b[i], b[i]});
        fq[b[i]]++;
        s.insert({(cc + 1) * b[i], b[i]});
      }else{
        fq[b[i]]++;
        s.insert({b[i], b[i]});
      }
      r += s.begin()->first;
      in.insert(s.begin()->second);
      s.erase(s.begin());
    }
    ans[i] = sm - r;
  }
  return ans;
}