Cod sursa(job #586094)

Utilizator Marius96Marius Gavrilescu Marius96 Data 30 aprilie 2011 13:40:59
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 2.92 kb
#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;
                ev.erase(it);
                ev.insert(make_pair(t+*it2,*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();
    }

    while(n){
        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();
            it=(++itt).base();
            ok=false;
            if(it->first>*it2+t){
                ok=true;
                ev.erase(it);
                ev.insert(make_pair(t+*it2,*it2));
            }
        }*/
        if(ev.size())t=ev.begin()->first;
    }
    printf("%d",t);
}