Submission #1005749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005749		12345678	A Plus B (IOI23_aplusb)	C++17	100 / 100	77 ms	14344 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) {
	vector<int> res;
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	set<pair<int, int>> s;
	s.insert({0, 0});
	pq.push({A[0]+B[0], {0, 0}});
	for (int i=0; i<N; i++)
	{
		auto t=pq.top();
		pq.pop();
		res.push_back(t.first);
		int a=t.second.first, b=t.second.second;
		if (a+1<N&&s.find({a+1, b})==s.end()) s.insert({a+1, b}), pq.push({A[a+1]+B[b], {a+1, b}});
		if (b+1<N&&s.find({a, b+1})==s.end()) s.insert({a, b+1}), pq.push({A[a]+B[b+1], {a, b+1}});
	}
	return res;
}

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