#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) {
priority_queue<pair<int, pair<int, int>>,
vector<pair<int, pair<int, int>>>,
greater<pair<int, pair<int, int>>>> pq;
pq.push({A[0] + B[0], {0, 0}});
vector<int> ans;
while (ans.size() < N) {
ans.push_back(pq.top().first);
pair<int, int> t = pq.top().second;
pq.pop();
if (t.second == 0) {
if (t.first + 1 < N) pq.push({A[t.first + 1] + B[0], {t.first + 1, 0}});
if (1 < N) pq.push({A[t.first] + B[1], {t.first, 1}});
}
else {
if (t.second + 1 < N) pq.push({A[t.first] + B[t.second + 1], {t.first, t.second + 1}});
}
}
return ans;
}
/*
(0, 0) -> (1, 0) -> (2, 0) -> ... -> (i, 0)
-> (i, 1) -> (i, 2) -> ... -> (i, j)
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |