Pagini recente » Borderou de evaluare (job #868561) | Cod sursa (job #2539687) | Borderou de evaluare (job #2235493) | Cod sursa (job #2375236) | Cod sursa (job #585453)
Cod sursa(job #585453)
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define ii pair<int, int>
#define mp make_pair
const int lg = 100002;
int n, m1, m2, timp[lg], last[lg], tmp1, tmp2, a[lg], b[lg], i, pz, next[lg], j;
ii rez;
bool ok(int s, int val){
int i, vf, ind = 0;
if (!s){
for (i = 1; i <= m1; i ++)
ind += val / a[i];
if (ind >= n)
return 1;
return 0;
}
priority_queue<ii, vector<ii> > hp;
for (i = 1; i <= m2; i ++)
hp.push(mp(val - b[i], i));
for (vf = n, i = 1; i <= n; i ++, vf --){
rez = hp.top(); hp.pop();
if (timp[vf] > rez.x)
return 0;
hp.push(mp(rez.x - b[ rez.y ], rez.y));
}
return 1;
}
int bs(int s){
int li = 1, ls = 1000000000, x, gs = -1;
while (li <= ls){
x = (li + ls) / 2;
if (ok(s, x) == 1){
gs = x;
ls = x - 1;
}
else
li = x + 1;
}
return gs;
}
int main()
{
freopen("fabrica.in", "rt", stdin);
freopen("fabrica.out", "wt", stdout);
scanf("%d%d%d", &n, &m1, &m2);
for (i = 1; i <= m1; i ++)
scanf("%d", &a[i]);
for (i = 1; i <= m2; i ++)
scanf("%d", &b[i]);
tmp1 = bs(0);
priority_queue<ii, vector<ii> > hp;
for (i = 1; i <= m1; i ++)
hp.push(mp(-a[i], i));
for (i = 1; i <= n; i ++){
rez = hp.top(); hp.pop();
timp[i] = -rez.x;
hp.push(mp(rez.x - a[ rez.y ], rez.y));
}
sort(timp + 1, timp + n + 1);
tmp2 = bs(1);
printf("%d %d\n", tmp1, tmp2);
return 0;
}