Pagini recente » Cod sursa (job #2301205) | Cod sursa (job #3140088) | Cod sursa (job #2569981) | Cod sursa (job #922067) | Cod sursa (job #586101)
Cod sursa(job #586101)
#include <fstream>
#include <set>
using namespace std;
const char InFile[]="fabrica.in";
const char OutFile[]="fabrica.out";
const int MaxNA=50111;
const int MaxNB=50111;
ifstream fin(InFile);
ofstream fout(OutFile);
struct proc
{
proc(int _t=0, int _p=0):t(_t),p(_p){}
int t,p;
};
bool operator< (const proc &a, const proc &b)
{
return a.t<b.t;
}
int N,NA,NB,VA[MaxNA],VB[MaxNB],solA,solAB;
multiset<int> freeA;
multiset<proc> runA;
multiset<int> freeB;
multiset<proc> runB;
inline bool goodA(int val)
{
freeA.clear();
runA.clear();
for(register int i=1;i<=NA;++i)
{
freeA.insert(VA[i]);
}
int n=N;
int t=0;
while(n)
{
bool ok=false;
while(!freeA.empty() && n)
{
int p=(*freeA.begin());
if(t+p>val)
{
break;
}
ok=true;
--n;
runA.insert(proc(t+p,p));
freeA.erase(freeA.begin());
}
if(!runA.empty())
{
t=runA.begin()->t;
while(!runA.empty())
{
if((*runA.begin()).t>t)
{
break;
}
ok=true;
freeA.insert(runA.begin()->p);
runA.erase(runA.begin());
}
}
if(!ok)
{
break;
}
}
return !n;
}
inline bool goodAB(int val)
{
freeA.clear();
runA.clear();
for(register int i=1;i<=NA;++i)
{
freeA.insert(VA[i]);
}
freeB.clear();
runB.clear();
for(register int i=1;i<=NB;++i)
{
freeB.insert(VB[i]);
}
int nA=N;
int nB=N;
int t=0;
int x=0;
while(nB)
{
bool ok=false;
while(!freeA.empty() && nA)
{
int p=(*freeA.begin());
if(t+p>val)
{
break;
}
ok=true;
--nA;
runA.insert(proc(t+p,p));
freeA.erase(freeA.begin());
}
while(!freeB.empty())
{
multiset<int>::iterator it=freeB.end();
--it;
if(t+*it<=val)
{
break;
}
freeB.erase(*it);
}
while(x)
{
if(freeB.empty())
{
break;
}
multiset<int>::iterator it=freeB.end();
--it;
int p=*it;
if(t+p>val)
{
break;
}
ok=true;
--nB;
runB.insert(proc(t+p,p));
freeB.erase(it);
--x;
}
int tp=2147483647;
if(!runA.empty())
{
tp=runA.begin()->t;
}
if(!runB.empty())
{
if(runB.begin()->t<tp)
{
tp=runB.begin()->t;
}
}
t=tp;
while(!runA.empty())
{
if((*runA.begin()).t>t)
{
break;
}
ok=true;
++x;
freeA.insert(runA.begin()->p);
runA.erase(runA.begin());
}
while(!runB.empty())
{
if((*runB.begin()).t>t)
{
break;
}
ok=true;
freeB.insert(runB.begin()->p);
runB.erase(runB.begin());
}
if(!ok)
{
break;
}
}
return !nB;
}
int main()
{
fin>>N>>NA>>NB;
for(register int i=1;i<=NA;++i)
{
fin>>VA[i];
}
for(register int i=1;i<=NB;++i)
{
fin>>VB[i];
}
fin.close();
int st=0;
int dr=2147483647;
while(st<=dr)
{
int mid=st+((dr-st)>>1);
if(goodA(mid))
{
dr=mid-1;
solA=mid;
}
else
{
st=mid+1;
}
}
st=0;
dr=2147483647;
while(st<=dr)
{
int mid=st+((dr-st)>>1);
if(goodAB(mid))
{
dr=mid-1;
solAB=mid;
}
else
{
st=mid+1;
}
}
fout<<solA<<" "<<solAB<<"\n";
fout.close();
return 0;
}