Pagini recente » Cod sursa (job #3180188) | Cod sursa (job #3283195) | Cod sursa (job #622452) | Cod sursa (job #1201606) | Cod sursa (job #586716)
Cod sursa(job #586716)
#include <cstdio>
#include <queue>
#include <algorithm>
#include <string>
#include <cstring>
#define MAXN 100005
using namespace std;
int A[MAXN], B[50005], N, nrA, nrB, vB[MAXN];
struct Point {
int x, y;
bool operator < (const Point &o) const {
return x + A[y] > o.x + A[o.y];
}
};
priority_queue <Point> Q1;
Point nod;
int mx, i, add;
vector <int> T, V;
int main ()
{
freopen ("fabrica.in", "r", stdin);
freopen ("fabrica.out", "w", stdout);
scanf ("%d %d %d\n", &N, &nrA, &nrB);
for (i = 1; i <= nrA; i++) {
scanf ("%d\n", &A[i]);
nod.x = 0; nod.y = i;
Q1.push (nod);
}
for (i = 1; i <= nrB; i++) {
scanf ("%d\n", &B[i]);
}
for (i = 1; i <= N; i++) {
nod = Q1.top ();
Q1.pop ();
nod.x += A[nod.y];
mx = max (mx, nod.x);
T.push_back (nod.x);
Q1.push (nod);
}
int ls, ld, mid, l, sol = 0;
sort (T.begin (), T.end ());
ls = 1; ld = 1 << 29;
while (ls <= ld) {
mid = (ls + ld) >> 1;
// printf ("%d %d %d\n", ls, mid, ld);
memset (vB, 0, sizeof (vB));
V = T;
int n = N - 1;
for (l = nrB; l >= 2 && n >= 0; l--) {
while (1)
{
if (n == -1) break;
int left, right, med, val;
left = 0; right = n;
int SS = -1;
while (left <= right) {
med = (left + right) >> 1;
val = max (V[med], vB[l]) + B[l];
if (val > mid)
right = med - 1;
else {
left = med + 1;
SS = med;
}
}
if (SS != -1) {
vB[l] = max (V[SS], vB[l]) + B[l];
V.erase (V.begin () + SS);
n -= 1;
/* if (mid == 10) {
for (int j = 0; j < V.size (); j++)
printf ("%d ", V[j]);
printf ("\n");
}
*/}
else break;
}
//printf ("%d ", vB[l]);
}
for (int j = 0; j <= n; j++)
vB[l] = max (vB[l], V[j]) + B[l];
if (vB[l] <= mid) {
sol = mid;
ld = mid - 1;
}
else ls = mid + 1;
}
printf ("%d %d\n", T[N - 1], sol);
return 0;
}