Pagini recente » Cod sursa (job #897384) | Cod sursa (job #1619471) | Cod sursa (job #1901287) | Cod sursa (job #2663935) | Cod sursa (job #585998)
Cod sursa(job #585998)
#include <cstdio>
#include <queue>
using namespace std;
struct timp
{
int start,add;
};
struct cmp
{
bool operator()(timp i,timp j)
{
return i.start+i.add>j.start+j.add;
}
};
struct cmp2
{
bool operator()(timp i,timp j)
{
return i.start<j.start;
}
};
timp aux;
priority_queue <timp,vector <timp>,cmp> v;
priority_queue <timp,vector <timp>,cmp2> v2;
int z[100001],y[100001],n,a,b;
int makesol (int x)
{
int i;
while (!v2.empty()) v2.pop();
for (i=1;i<=b;++i)
{
aux.start=x-y[i];
aux.add=y[i];
v2.push(aux);
}
for (i=n;i>0;--i)
{
aux=v2.top();
if (aux.start<z[i])
return 0;
v2.pop();
aux.start-=aux.add;
v2.push(aux);
}
return 1;
}
int main()
{
int sol,x,i;
freopen("fabrica.in","r",stdin);
freopen("fabrica.out","w",stdout);
scanf("%d%d%d",&n,&a,&b);
for (i=1;i<=a;++i)
{
scanf("%d",&x);
aux.add=x;
v.push(aux);
}
for (i=1;i<=b;++i)
scanf("%d",&y[i]);
for (i=1;i<=n;++i)
{
aux=v.top();
z[i]+=aux.start+aux.add;
v.pop();
aux.start+=aux.add;
v.push(aux);
}
printf("%d ",z[n]);
sol=2147483647;
for (x=1073741824;x>0;x>>=1)
if (makesol(sol-x))
sol-=x;
printf("%d",sol);
return 0;
}