Pagini recente » Cod sursa (job #2521709) | Cod sursa (job #2138314) | Cod sursa (job #2211631) | Cod sursa (job #170885) | Cod sursa (job #585984)
Cod sursa(job #585984)
#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;
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;
}
freeA.insert(runA.begin()->p);
runA.erase(runA.begin());
}
}
if(!ok)
{
break;
}
}
return !n;
}
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;
}
}
fout<<solA<<" "<<solAB<<"\n";
fout.close();
return 0;
}