Cod sursa(job #585924)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 30 aprilie 2011 12:41:28
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.27 kb
#include <algorithm>
#include <cstring>
#include <fstream>

using namespace std;

const int Dim = 100001;
const int Inf = 2000000001;

int N, Na, Nb;
int texa[Dim >> 1], texb[Dim >> 1], tfproc[Dim >> 1], tf[Dim], heap[Dim >> 1];

void UpH( int nod ) {

    int aux;

    while( nod > 1 ) {

        aux = nod >> 1;
        if( tfproc[heap[nod]] < tfproc[heap[aux]] ) {

            swap( heap[nod], heap[aux] );
            nod = aux;
        }
        else
            return;
    }
}

void DownH( int nod ) {

    int aux;

    while( nod < heap[0] ) {

        if( (nod << 1) <= heap[0] ) {

            aux = nod << 1;
            if( aux + 1 <= heap[0] && tfproc[heap[aux + 1]] < tfproc[heap[aux]] )
                ++aux;
        }
        else
            return;
        if( tfproc[heap[nod]] > tfproc[heap[aux]] ) {

            swap( heap[nod], heap[aux] );
            nod = aux;
        }
        else
            return;
    }
}

void HPush( int x ) {

    heap[++heap[0]] = x;
    UpH( heap[0] );
}

void HPop() {

    heap[1] = heap[heap[0]--];
    DownH( 1 );
}

int main() {

    ifstream fin( "fabrica.in" );
    ofstream fout( "fabrica.out" );

    int i, id, mx;

    fin >> N;
    fin >> Na, fin >> Nb;
    for( i = 1; i <= Na; ++i )
        fin >> texa[i];
    for( i = 1; i <= Nb; ++i )
        fin >> texb[i];

    for( i = 1; i <= Na; ++i ) {

        tfproc[i] = texa[i];
        HPush( i );
    }
    for( i = 1; i <= N; ++i ) {

        id = heap[1];
        HPop();
        tf[i] = tfproc[id];
        tfproc[id] += texa[id];
        HPush( id );
    }
    mx = -Inf;
    for( i = 1; i <= Na; ++i )
        mx = max( mx, tfproc[i] - texa[i] );

    //prima cerinta
    fout << mx << " ";

    memset( heap, 0, sizeof( heap ) );
    for( i = 1; i <= Nb; ++i ) {

        tfproc[i] = texb[i];
        HPush( i );
    }
    for( i = 1; i <= N; ++i ) {

        id = heap[1];
        HPop();
        tfproc[id] = max( tfproc[id] - texb[id], tf[i] ) + 2 * texb[id];
        HPush( id );
    }
    mx = -Inf;
    for( i = 1; i <= Nb; ++i )
        mx = max( mx, tfproc[i] - texb[i] );

    //a doua cerinta
    fout << mx;

    fin.close();
    fout.close();

    return 0;
}