| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1357841 | po_rag526 | A Plus B (IOI23_aplusb) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#include "aplusb.h"
struct A{
long long i,j,x;
bool operator<(const A&o)const{
return x>o.x;
}
};
priority_queue<A>pq;
bitset<10000>mark[10000];
bitset<10000>vis[10000];
std::vector<int> smallest_sums(int N, std::vector<int> A, std::vector<int> B) {
vector<int>ret;
pq.push({0,0,A[0]+B[0]});
vis[0][0]=1;
int n = A.size();
int m = B.size();
while(ret.size() != N){
int i = pq.top().i,j = pq.top().j , v = pq.top().x;
pq.pop();
if(mark[i][j])continue;
mark[i][j]=1;
ret.push_back(v);
if(i+1<n && mark[i+1][j]==0 && vis[i+1][j]==0){
pq.push({i+1,j,A[i+1]+B[j]});
vis[i+1][j]=1;
}
if(j+1<m && mark[i][j+1]==0 && vis[i][j+1]==0){
pq.push({1,j+1,A[i]+B[j+1]});
vis[i][j+1]=1;
}
}
return ret;
}
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> A(N);
for (int i = 0; i < N; ++i)
assert(1 == scanf("%d", &A[i]));
std::vector<int> B(N);
for (int i = 0; i < N; ++i)
assert(1 == scanf("%d", &B[i]));
fclose(stdin);
std::vector<int> res = smallest_sums(N, A, B);
int n = res.size();
for (int i = 0; i < n; ++i) {
if (i > 0)
printf(" ");
printf("%d", res[i]);
}
printf("\n");
fclose(stdout);
return 0;
}
