Submission #933364

#	Time	Username	Problem	Language	Result	Execution time	Memory
933364		sleepntsheep	A Plus B (IOI23_aplusb)	C++17	100 / 100	82 ms	10332 KiB

aplusb

#include "aplusb.h"
#include <set>
#include <tuple>
#include <map>
#include <utility>
#include <queue>

std::vector<int> smallest_sums(int n, std::vector<int> a, std::vector<int> b)
{
    std::vector<int> c(n);

    std::priority_queue<std::tuple<int, int, int>> q;
    q.emplace(-a[0] + -b[0], 0, 0);
    std::set<std::tuple<int, int>> ss;
    for (int k=0;k<n;)
    {
        auto [aa,i,j]=q.top();q.pop();
        if (ss.count({i, j})) continue;
        ss.insert({i, j});
        c[k]=-aa;
        if(i+1<n) q.emplace(-a[i+1]+-b[j],i+1,j);
        if(j+1<n) q.emplace(-a[i]+-b[j+1],i,j+1);
        ++k;
    }

	return c;
}

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