Pagini recente » Cod sursa (job #2729918) | Cod sursa (job #2255993) | Cod sursa (job #3242684) | Cod sursa (job #1981010) | Cod sursa (job #586053)
Cod sursa(job #586053)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
#include <set>
using namespace std;
#define Nmax 100010
#define Mmax 50010
#define INF 0x3f3f3f3f
int n, Na, Nb;
int A[Mmax], B[Mmax], T[Nmax], Sol[Nmax];
int H1[Nmax], H2[Nmax];
int Cst[Nmax];
int N1, N2;
void up_heap1 (int p) {
int t, c = p, aux;
t = c >> 1;
while (t && Cst[ H1[t] ] + A[ H1[t] ] > Cst[ H1[c] ] + A[ H1[c] ]) {
aux = H1[t];
H1[t] = H1[c];
H1[c] = aux;
c = t;
t = c >> 1;
}
}
void up_heap2 (int p) {
int t, c = p, aux;
t = c >> 1;
while (t && A[ H2[t] ] > A[ H2[c] ]) {
aux = H2[t];
H2[t] = H2[c];
H2[c] = aux;
c = t;
t = c >> 1;
}
}
void down_heap1 (int p) {
int t = p, c, aux;
c = t << 1;
if (c < N1 && Cst[ H1[c + 1] ] + A[ H1[c + 1] ] < Cst[ H1[c + 1] ] + A[ H1[c + 1] ]) c++;
while (c <= N1 && Cst[ H1[t] ] + A[ H1[t] ] > Cst[ H1[c] ] + A[ H1[c] ]) {
aux = H1[t];
H1[t] = H1[c];
H1[c] = aux;
t = c;
c = t << 1;
if (c < N1 && Cst[ H1[c + 1] ] + A[ H1[c + 1] ] < Cst[ H1[c + 1] ] + A[ H1[c + 1] ]) c++;
}
}
void down_heap2 (int p) {
int t = p, c, aux;
c = t << 1;
if (c < N2 && A[ H2[c + 1] ] < A[ H2[c + 1] ]) c++;
while (c <= N2 && A[ H2[t] ] > A[ H2[c] ]) {
aux = H2[t];
H2[t] = H2[c];
H2[c] = aux;
t = c;
c = t << 1;
if (c < N2 && A[ H2[c + 1] ] < A[ H2[c + 1] ]) c++;
}
}
void rezolva () {
int i, c1, c2;
sort (T + 1, T + n + 1);
N1 = N2 = 0;
for (i = 1; i <= Na; i++) {
H1[++N1] = i;
Cst[i] = 0;
up_heap1 (N1);
}
for (i = 1; i <= n; i++) {
while (N1 && Cst[ H1[1] ] < T[i]) {
H2[++N2] = H1[1];
up_heap2 (N2);
H1[1] = H1[N1];
N1--;
down_heap1 (1);
}
c1 = INF; c2 = INF;
if (N1)
c1 = Cst[H1[1]] + A[ H1[1] ];
if (N2)
c2 = T[i] + A[ H2[1] ];
if (c1 <= c2) {
Sol[i] = c1;
Cst[ H1[1] ] = c1;
down_heap1 (1);
}
else {
Sol[i] = c2;
Cst[ H2[1] ] = c2;
if ( Cst[ H2[1] ] > T[i + 1] && i < n ) {
H1[ ++N1 ] = H2[1];
up_heap1 (N1);
H2[1] = H2[N2];
N2--;
down_heap2 (1);
}
else {
down_heap2 (1);
}
}
}
}
void citire () {
int i;
scanf ("%d %d %d", &n, &Na, &Nb);
for (i = 1; i <= Na; i++)
scanf ("%d", &A[i]);
for (i = 1; i <= Nb; i++)
scanf ("%d", &B[i]);
}
int main () {
freopen ("fabrica.in", "r", stdin);
freopen ("fabrica.out", "w", stdout);
citire ();
rezolva ();
memcpy (T, Sol, sizeof (Sol));
int i;
long long sol = 0;
for (i = 1; i <= n; i++)
if (sol < Sol[i]) sol = Sol[i];
printf ("%lld ", sol);
Na = Nb;
mempcpy (B, A, sizeof (B)); //
rezolva ();
sol = 0;
for (i = 1; i <= n; i++)
if (sol < Sol[i]) sol = Sol[i];
printf ("%lld\n", sol);
return 0;
}