Pagini recente » Cod sursa (job #657814) | Cod sursa (job #2189834) | Cod sursa (job #2221270) | Cod sursa (job #3126009) | Cod sursa (job #2401881)
#include<fstream>
#define DIM 50005
#define f first
#define s second
#define INF 2000000000
using namespace std;
int n, a, b, i, maxim, ind;
int va[DIM], vb[DIM], t[2 * DIM], poz[4][DIM];
pair<int, int> h[4][DIM];
ifstream fin("fabrica.in");
ofstream fout("fabrica.out");
void upd(int t, int pos){
int c = pos, p = c / 2;
while(p > 0 && h[t][p].f > h[t][c].f){
swap(h[t][p], h[t][c]);
poz[t][ h[t][p].s ] = p;
poz[t][ h[t][c].s ] = c;
c = p;
p = c / 2;
}
}
void elim(int t, int pos, int n){
int p = pos, c = p + p;
while(c <= n){
if(c + 1 <= n && h[t][c].f > h[t][c + 1].f){
c++;
}
if(h[t][p].f > h[t][c].f){
swap(h[t][p], h[t][c]);
poz[t][ h[t][p].s ] = p;
poz[t][ h[t][c].s ] = c;
p = c;
c = 2 * p;
}
else{
break;
}
}
}
int main(){
fin>> n >> a >> b;
for(i = 1; i <= a; i++){
fin>> va[i];
h[0][i] = make_pair(va[i], i);
poz[0][i] = i;
upd(0, i);
}
for(i = 1; i <= b; i++){
fin>> vb[i];
poz[1][i] = poz[2][i] = poz[3][i] = i;
h[1][i] = make_pair(vb[i], i);
upd(1, i);
h[2][i] = h[3][i] = make_pair(INF, i);
}
for(i = 1; i <= n; i++){
t[i] = h[0][1].f;
h[0][1].f += va[ h[0][1].s ];
elim(0, 1, a);
}
for(i = 1; i <= n; i++){
while(h[2][1].f < t[i]){
ind = h[2][1].s;
h[1][ poz[1][ind] ].f = vb[ind];
h[2][ poz[2][ind] ].f = h[3][ poz[3][ind] ].f = INF;
upd(1, poz[1][ind]);
elim(2, poz[2][ind], b);
elim(3, poz[3][ind], b);
}
if(t[i] + h[1][1].f < h[3][1].f){
maxim = t[i] + h[1][1].f;
ind = h[1][1].s;
h[1][1].f = INF;
elim(1, 1, b);
h[2][ poz[2][ind] ].f = t[i] + vb[ind];
h[3][ poz[3][ind] ].f = t[i] + 2 * vb[ind];
upd(2, poz[2][ind]);
upd(3, poz[3][ind]);
}
else{
maxim = h[3][1].f;
ind = h[3][1].s;
h[2][ poz[2][ind] ].f += vb[ind];
h[3][ poz[3][ind] ].f += vb[ind];
elim(2, poz[2][ind], b);
elim(3, poz[3][ind], b);
}
}
fout<< t[n] <<" "<< maxim <<"\n";
return 0;
}