Submission #74999387

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef unsigned __int128 ulll;

void solve() {
    int n,m,k;
    cin >> n >> m >> k;
    vector<ll> a(n),b(m);
    for (auto &x : a) {
        cin >> x;
    }
    for (auto &x : b) {
        cin >> x;
    }
    sort(a.rbegin(),a.rend());
    sort(b.rbegin(),b.rend());
    ll ans = 0;
    priority_queue<tuple<ll,int,int>> pq;
    set<pair<int,int>> hashi;
    hashi.insert({0,0});
    pq.push({a[0]*b[0],0,0});
    for (int i = 0;i < k;i++) {
        auto [res,ai,bi] = pq.top();
        ans += res;
        pq.pop();
        if (ai+1 < n && !hashi.count({ai+1,bi})) {
            pq.push({a[ai+1]*b[bi],ai+1,bi});
            hashi.insert({ai+1,bi});
        }
        if (bi+1 < m && !hashi.count({ai,bi+1})) {
            pq.push({a[ai]*b[bi+1],ai,bi+1});
            hashi.insert({ai,bi+1});
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Submission Info

Judge Result