Submission #842622

#	Time	Username	Problem	Language	Result	Execution time	Memory
842622		WLZ	A Plus B (IOI23_aplusb)	C++17	100 / 100	108 ms	10436 KiB

aplusb

#include "aplusb.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> smallest_sums(int n, std::vector<int> a, std::vector<int> b) {
    sort(a.begin(), a.end()); sort(b.begin(), b.end());
    vector<int> ans;
    set< pair<int, int> > st = {};
    priority_queue< tuple<int, int, int>, vector< tuple<int, int, int> >, greater<> > pq; pq.push({a[0] + b[0], 0, 0});
    while ((int) ans.size() < n) {
        int x = get<0>(pq.top()), i = get<1>(pq.top()), j = get<2>(pq.top());
        pq.pop();
        if (st.count({i, j})) continue;
        st.insert({i, j});
        ans.push_back(x);
        if (i < n - 1) pq.push({a[i + 1] + b[j], i + 1, j});
        if (j < n - 1) pq.push({a[i] + b[j + 1], i, j + 1});
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40