Pagini recente » Cod sursa (job #1652455) | Cod sursa (job #85339) | Cod sursa (job #18527) | Cod sursa (job #1832206) | Cod sursa (job #586477)
Cod sursa(job #586477)
#include<cstdio>
#include<map>
#include<set>
#include<deque>
#include<algorithm>
using namespace std;
multimap<int,int> ev;
multiset<int> idle;
int va[50005],vb[50005];
deque<int> v;
int main(){
freopen("fabrica.in","r",stdin);
freopen("fabrica.out","w",stdout);
int n,na,nb;
scanf("%d%d%d",&n,&na,&nb);
for(int i=0;i<na;i++)
scanf("%d",va+i);
for(int i=0;i<nb;i++)
scanf("%d",vb+i);
sort(va,va+na);sort(vb,vb+nb);
int nn=n,t=0;
for(int i=0;i<na;i++)
idle.insert(va[i]);
while(nn||ev.size()){
multimap<int,int>::iterator it;
while(ev.size()&&(it=ev.begin())->first==t){
idle.insert(it->second);
v.push_back(it->first);
ev.erase(it);
}
for(multiset<int>::iterator it=idle.begin();nn&&it!=idle.end();){
if(ev.size()){
multimap<int,int>::reverse_iterator itt=ev.rbegin();
ev.insert((++itt).base(),make_pair(t+*it,*it));
}
else
ev.insert(make_pair(t+*it,*it));
it++;
idle.erase(idle.begin());
nn--;
}
multiset<int>::iterator it2;bool ok=true;
while(idle.size()&&ev.size()&&ok){
it2=idle.begin();
multimap<int,int>::reverse_iterator itt=ev.rbegin();
it=(++itt).base();
ok=false;
if(it->first>*it2+t){
ok=true;
idle.insert(it->second);
ev.erase(it);
ev.insert(make_pair(t+*it2,*it2));
idle.erase(it2);
}
}
if(ev.size())t=ev.begin()->first;
}
printf("%d ",t);
nn=t=0;
while(v.size()){
ev.insert(make_pair(v.front(),-1));
v.pop_front();
}
idle.clear();
for(int i=0;i<nb;i++)
idle.insert(vb[i]);
while(n||ev.size()){
multimap<int,int>::iterator it;
while(ev.size()&&(it=ev.begin())->first==t){
if(it->second==-1){
nn++;
ev.erase(it);
continue;
}
idle.insert(it->second);
v.push_back(it->first);
ev.erase(it);
}
for(multiset<int>::iterator it=idle.begin();nn&&it!=idle.end();){
if(ev.size()){
multimap<int,int>::reverse_iterator itt=ev.rbegin();
ev.insert((++itt).base(),make_pair(t+*it,*it));
}
else
ev.insert(make_pair(t+*it,*it));
it++;
idle.erase(idle.begin());
nn--;n--;
v.pop_front();
}
multiset<int>::iterator it2;bool ok=true;
while(idle.size()&&ev.size()&&ok){
it2=idle.begin();
multimap<int,int>::reverse_iterator itt=ev.rbegin();
while(itt!=ev.rend()&&itt->second==-1)itt++;
if(itt==ev.rend())break;
it=(++itt).base();
ok=false;
if(it->first>*it2+t){
ok=true;
idle.insert(it->second);
ev.erase(it);
ev.insert(make_pair(t+*it2,*it2));
idle.erase(it2);
}
}
if(ev.size())t=ev.begin()->first;
}
printf("%d",t);
}