Pagini recente » Cod sursa (job #1995288) | Cod sursa (job #786312) | Cod sursa (job #1230895) | Cod sursa (job #3189648) | Cod sursa (job #586074)
Cod sursa(job #586074)
#include <stdio.h>
#define NMax 100005
FILE *fin = fopen("fabrica.in", "rt");
FILE *fout = fopen("fabrica.out", "wt");
int n, nra, nrb, oa[NMax], ob[NMax];
int a[NMax], b[NMax];
typedef struct doz
{
int tip; // 0 - A, 1 - B
int ind; // ind in a[] or b[]
int ready; // ready time
}doz;
doz h[NMax];
int hs;
void insert(doz d);
doz getTop();
void intersch(int p1, int p2);
int main()
{
fscanf(fin, "%d %d %d", &n, &nra, &nrb);
for (int i = 0; i < nra; i++)
fscanf(fin, "%d", &a[i]);
for (int i = 0; i < nrb; i++)
fscanf(fin, "%d", &b[i]);
for (int i = 0; i < nra; i++)
{
doz d;
d.tip = 0;
d.ind = i;
d.ready = a[i];
insert(d);
}
for (int i = 0; i < n; i++)
{
doz d = getTop();
oa[i] = d.ready;
d.ready += a[d.ind];
insert(d);
}
fprintf(fout, "%d ", oa[n-1]);
hs = 0;
for (int i = 0; i < nrb; i++)
{
doz d;
d.tip = 1;
d.ind = i;
d.ready = b[i];
insert(d);
}
for (int i = 0; i < n; i++)
{
doz d = getTop();
ob[i] = d.ready + oa[0];
d.ready += b[d.ind];
insert(d);
}
fprintf(fout, "%d\n", ob[n - 1]);
fclose(fin);
fclose(fout);
return 0;
}
void insert(doz d)
{
h[hs] = d;
int p = hs;
while (h[p / 2].ready > h[p].ready)
{
intersch(p / 2, p);
p /= 2;
}
hs++;
}
doz getTop()
{
doz rez = h[0];
int p = 0, p1, p2;
h[0] = h[hs - 1];
hs--;
while (p < hs)
{
p1 = 2 * p + 1;
p2 = 2 * p + 2;
if (p2 < hs && h[p2].ready < h[p1].ready)
p1 = p2;
if (p1 >= hs)
break;
if (h[p].ready > h[p1].ready)
{
intersch(p, p1);
p = p1;
}
else
{
break;
}
}
return rez;
}
void intersch(int p1, int p2)
{
doz aux = h[p1];
h[p1] = h[p2];
h[p2] = aux;
}