Pagini recente » Cod sursa (job #564034) | Cod sursa (job #2440691) | Cod sursa (job #1236547) | Cod sursa (job #451015) | Cod sursa (job #1347128)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("fabrica.in");
ofstream fout("fabrica.out");
int N, NRA, NRB;
int bereA[100005], bereB[100005];
int solA, solB;
int lgA, lgB;
struct heap
{
int val, valinit;
};
heap A[100005], B[100005];
int father(int nod)
{
return nod / 2;
}
int left_son(int nod)
{
return nod * 2;
}
int right_son(int nod)
{
return nod * 2 + 1;
}
void urca(heap H[], int nod)
{
while (nod > 1 && (H[nod].val < H[father(nod)].val || (H[nod].val == H[father(nod)].val && H[nod].valinit < H[father(nod)].valinit)))
{
swap(H[nod].val, H[father(nod)].val);
nod = father(nod);
}
}
void coboara(heap H[], int lg, int nod)
{
int son = 1;
while (son)
{
son = 0;
if (left_son(nod) <= lg)
{
son = left_son(nod);
if (right_son(nod) <= lg && (H[right_son(nod)].val < H[son].val || (H[right_son(nod)].val == H[son].val && H[right_son(nod)].valinit < H[son].valinit)))
son = right_son(nod);
if (H[son].val >= H[nod].val)
son = 0;
if (son)
{
swap(H[nod], H[son]);
nod = son;
}
}
}
}
void insert(heap H[], int& lg, int val, int valinit)
{
++lg;
H[lg].val = val;
H[lg].valinit = valinit;
urca(H, lg);
}
void cut(heap H[], int& lg, int nod)
{
H[nod] = H[lg];
--lg;
coboara(H, lg, nod);
}
int main()
{
fin >> N >> NRA >> NRB;
for (int i = 1, x; i <= NRA; ++i)
{
fin >> x;
insert(A, lgA, x, x);
}
for (int i = 1; i <= N; ++i)
{
bereA[i] = A[1].val;
insert(A, lgA, A[1].val + A[1].valinit, A[1].valinit);
cut(A, lgA, 1);
}
for (int i = 1, x; i <= NRB; ++i)
{
fin >> x;
insert(B, lgB, x, x);
}
for (int i = 1; i <= N; ++i)
{
bereB[i] = B[1].val;
insert(B, lgB, B[1].val + B[1].valinit, B[1].valinit);
cut(B, lgB, 1);
}
for (int i = 1; i <= N; ++i)
{
solA = max(solA, bereA[i]);
solB = max(solB, bereA[i] + bereB[N - i + 1]);
}
fout << solA << ' ' << solB << '\n';
fin.close();
fout.close();
return 0;
}