Cod sursa(job #586221)

Utilizator MciprianMMciprianM MciprianM Data 30 aprilie 2011 14:08:27
Problema Fabrica Scor 12
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Open Marime 2.13 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const unsigned maxn = 50009;
priority_queue <pair<unsigned,unsigned>, vector<pair<unsigned,unsigned> >, greater<pair<unsigned,unsigned> > >q, qb1, qb2;
unsigned a [ maxn ], b [ maxn ];
unsigned tf [ maxn ];
unsigned tf2 [ maxn ];

int main (){
    int n, na, nb, i;
    ifstream f ( "fabrica.in" );
    f >> n >> na >> nb;
    unsigned int maxb ( 0 ), ti, maxs ( 0 );
    for ( i = 0; i < na; ++ i ) {
        f >> ti;
        q.push(make_pair(ti, i ) );
        a [ i ] = ti;
    }
    for ( i = 0; i < nb; ++ i ) {
        f >> ti;
        b [ i ] = ti;
    }
    pair<unsigned,unsigned> v, v2;
    for ( i = 0; i < n; ++ i ){
        v = q.top();
        q.pop();
        maxb = max ( maxb, v.first );
        tf [ i ] = v.first;
        v.first += a [ v.second ];
        q.push(v);
    }

    //
    for ( i = 0; i < nb; ++ i )
        qb1.push(make_pair ( b[i],i ));
    unsigned minf, indd;
    for ( i = 0; i < n; ++ i ){
        minf = -1;
        if ( !qb1.empty() ){
            v = qb1.top();
            if ( minf > v.first + tf [ i ] ){
                indd = 0;
                minf = v.first + tf [ i ];
            }
        }
        if ( !qb2.empty() ){
            v = qb2.top();
            if ( minf > v.first ){
                indd = 1;
                minf = v.first;
            }
        }
        maxs = max ( maxs, minf );
        tf2 [ i ] = minf;
        if ( indd ){
            v = qb2.top();
            qb2.pop();
        }
        else {
            v = qb1.top();
            v . first += tf [ i ];
            qb1.pop();
        }
        v.first+=b[v.second];
        if ( v.first - b [ v.second ] > tf [ i + 1 ] ){
            qb2.push ( v );
        }
        else{
            v.first = b [ v.second ];
            qb1.push(v);
        }
        while ( !qb2.empty() && qb2.top().first - b [ qb2.top().second ] <= tf [ i + 1 ] ) {
            v = qb2.top();
            v.first = b [ v.second ];
            qb1.push(v);
            qb2.pop();
        }
    }
    ofstream g("fabrica.out");
    g << maxb << " " << maxs << endl;
    g.close();
    return 0;
}