Pagini recente » Cod sursa (job #673232) | Cod sursa (job #1838602) | Cod sursa (job #2291272) | Cod sursa (job #1026352) | Cod sursa (job #585845)
Cod sursa(job #585845)
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
#define N_MAX 50005
#define INF (1<<30)
int costa[N_MAX],costb[N_MAX];
int finish[N_MAX];
int finish2[N_MAX];
int dim[N_MAX];
bool ut[N_MAX];
set <int> S[N_MAX];
struct cmp
{
bool operator () (const int a,const int b) const
{
return finish[a]+costa[a]>finish[b]+costa[b]||finish[a]+costa[a]==finish[b]+costa[b]&&costa[a]>costa[b];
}
};
struct cmp2
{
bool operator () (const int a,const int b) const
{
return finish2[a]+costb[a]>finish2[b]+costb[b]||finish2[a]+costb[a]==finish2[b]+costb[b]&&costb[a]>costb[b];
}
};
struct cmp3
{
bool operator () (const int a,const int b) const
{
return a>b;
}
};
priority_queue <int,vector <int>,cmp> PQ1;
priority_queue <int,vector <int>,cmp2 > PQ2;
priority_queue <int,vector <int>,cmp3 > PQ3;
int n,nra,nrb,i,j;
int sol1,sol2;
int main()
{
freopen("fabrica.in","r",stdin);
freopen("fabrica.out","w",stdout);
scanf("%d%d%d",&n,&nra,&nrb);
for(i=1;i<=nra;i++)
scanf("%d",&costa[i]);
for(i=1;i<=nrb;i++)
scanf("%d",&costb[i]);
sort(costa+1,costa+nra+1);
sort(costb+1,costb+nrb+1);
int umplere=0,scoase=0;
for(i=1;i<=nra;i++)
{
dim[i]=1;
PQ1.push(i);
}
while(1)
{
if(umplere<n||scoase<n)
{
int nod=PQ1.top();
if(dim[nod])
{
PQ1.pop();
dim[nod]--;
scoase+=ut[nod];
if(ut[nod])
{
PQ3.push(finish[nod]);
}
ut[nod]=1;
}
if(scoase==n)
break;
if(umplere==n)
continue;
finish[nod]+=costa[nod];
dim[nod]++;
PQ1.push(nod);
umplere++;
}
else
{
break;
}
}
memset(dim,0,sizeof(dim));
memset(ut,0,sizeof(ut));
for(i=1;i<=nrb;i++)
{
dim[i]=1;
PQ2.push(i);
}
while(!PQ3.empty())
{
int timp=PQ3.top();
PQ3.pop();
int nod=PQ2.top();
if(dim[nod])
{
PQ2.pop();
dim[nod]--;
}
finish2[nod]=max(finish2[nod],timp)+costb[nod];
dim[nod]++;
PQ2.push(nod);
}
for(i=1;i<=nra;i++)
sol1=max(sol1,finish[i]);
for(i=1;i<=nrb;i++)
sol2=max(sol2,finish2[i]);
printf("%d %d\n",sol1,sol2);
return 0;
}