Pagini recente » Cod sursa (job #29205) | Cod sursa (job #1815454) | Cod sursa (job #2988818) | Cod sursa (job #1126820) | Cod sursa (job #585954)
Cod sursa(job #585954)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define Nmax 100010
#define Mmax 50010
struct HEAP {
int t;
int nod;
} H[Mmax], aux;
int n, Na, Nb, Nh;
int A[Mmax], B[Mmax];
int T[Nmax], Sol[Nmax];
void up_heap (int p) {
int t, c = p;
t = c >> 1;
while ( t && H[t].t > H[c].t) {
aux = H[t];
H[t] = H[c];
H[c] = aux;
t = c;
c = t >> 1;
}
}
void down_heap (int p) {
int t = p, c;
c = t << 1;
if (c < Nh && H[c + 1].t < H[c].t) c++;
while (c <= Nh && H[t].t > H[c].t) {
aux = H[t];
H[t] = H[c];
H[c] = aux;
t = c;
c = t << 1;
if (c < Nh && H[c + 1].t < H[c].t) c++;
}
}
void rezolva (int T[], int N, int A[]) {
sort (T + 1, T + n + 1);
int i;
Nh = 0;
for (i = 1; i <= N; i++) {
H[++Nh].t = A[i];
H[Nh].nod = i;
up_heap (Nh);
}
for (i = 1; i <= n; i++) {
Sol[i] = H[1].t;
H[1].t = Sol[i] + (long long) A[ H[1].nod ];
down_heap (1);
}
}
int cont (int X) {
int i, j, x;
for (i = 1, j = 1; i <= Nb; i++) {
x = 0;
if (T[j] > x) x = T[j];
while (j <= n && x + B[i] <= X) {
x+= B[i];
j++;
if (T[j] > x) x = T[j];
}
if (j > n) return 1;
}
return 0;
}
void cauta () {
sort (T, T + n + 1);
int p = 1, u = (1 << 30), mij, sol;
while (p <= u) {
mij = (p + u) >> 1;
if ( cont (mij) ) {
sol = mij;
u = mij - 1;
}
else
p = mij + 1;
}
printf ("%d ", sol);
}
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 (T, Na, A);
memcpy (T, Sol, sizeof (Sol));
int i;
int sol = 0;
for (i = 1; i <= n; i++)
if (sol < Sol[i]) sol = Sol[i];
printf ("%d ", sol);
cauta ();
return 0;
}