Pagini recente » Cod sursa (job #2017638) | Cod sursa (job #1346906) | Cod sursa (job #1344238) | Cod sursa (job #1787556) | Cod sursa (job #1992425)
#include <cstdio>
#include <set>
using namespace std;
int x, n, nra, nrb, L, Heap[100005], p[100005], t[100005], aux[100005];
multiset <int> ma;
multiset <int> mb;
inline void pop(int x){
int y = 0;
while(x != y){
y = x;
if(y * 2 <= L && t[Heap[y * 2]] < t[Heap[x]]) x = y * 2;
if(y * 2 + 1 <= L && t[Heap[y * 2 + 1]] < t[Heap[x]]) x = y * 2 + 1;
int aux = Heap[x];
Heap[x] = Heap[y];
Heap[y] = aux;
}
}
inline void push(int x){
while(x / 2 && t[Heap[x]] < t[Heap[x / 2]]){
int aux = Heap[x];
Heap[x] = Heap[x / 2];
Heap[x / 2] = aux;
x /= 2;
}
}
int main()
{
freopen("fabrica.in", "r", stdin);
freopen("fabrica.out", "w", stdout);
scanf("%d%d%d", &n, &nra, &nrb);
for(int i = 1; i <= nra ; ++i){
scanf("%d", &x);
ma.insert(x);
}
for(int i = 1; i <= nrb ; ++i){
scanf("%d", &x);
mb.insert(x);
}
multiset <int> :: iterator it;
int time = 0, nr = 0;
for(int i = 1; i <= n ; ++i){
int cr = time;
if(!ma.empty()){
it = ma.begin();
cr = *it + time;
}
if((ma.empty() || (cr) > t[Heap[1]]) && L > 0){
time = t[Heap[1]];
while(L > 0 && (t[Heap[1]] <= time || t[Heap[1]] <= cr)){
ma.insert(aux[Heap[1]]);
Heap[1] = Heap[L--];
pop(1);
}
}
it = ma.begin();
p[i] = time + (*it);
Heap[++L] = ++nr;
aux[nr] = *it;
t[nr] = *it + time;
ma.erase(it);
}
int Sol = p[1];
for(int i = 2; i <= n ; ++i) if(p[i] > Sol) Sol = p[i];
printf("%d ", Sol);
L = 0; time = 0; nr = 0;
for(int i = n; i >= 1 ; --i){
int cr = time;
if(!mb.empty()){
it = mb.begin();
cr = *it + time;
}
if((mb.empty() || (cr) > t[Heap[1]]) && L > 0){
time = t[Heap[1]];
while(L > 0 && (t[Heap[1]] <= time || t[Heap[1]] <= cr)){
mb.insert(aux[Heap[1]]);
Heap[1] = Heap[L--];
pop(1);
}
}
it = mb.begin();
p[i] += time + (*it);
Heap[++L] = ++nr;
aux[nr] = *it;
t[nr] = *it + time;
mb.erase(it);
}
Sol = p[1];
for(int i = 2; i <= n ; ++i) if(p[i] > Sol) Sol = p[i];
printf("%d", Sol);
return 0;
}