Pagini recente » Cod sursa (job #127501) | Cod sursa (job #2414888) | Cod sursa (job #1691519) | Cod sursa (job #2512331) | Cod sursa (job #585924)
Cod sursa(job #585924)
#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;
}