Cod sursa(job #956576)

Utilizator sbasrikSemih Basrik sbasrik Data 3 iunie 2013 14:23:28
Problema Fabrica Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<list>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<climits>
#include<ctime>
#include<sstream>
#define mp       	make_pair
#define pb       	push_back
#define st       	first
#define nd       	second
#define wait     	getchar();getchar();
#define lint     	long long
#define KARE(a)	 	( (a)*(a) )
#define MAX(a,b) 	( (a)>(b) ? (a) : (b) )
#define MIN(a,b) 	( (a)<(b) ? (a) : (b) )
#define MAX3(a,b,c)	( MAX( a,MAX(b,c) ) )
#define MIN3(a,b,c)	( MIN( a,MIN(b,c) ) )
#define FILL(ar,a)	memset( ar,a,sizeof ar )
#define oo	 		1e9
#define pii       	pair<int,int>
#define pll			pair<lint,lint>
#define pdd			pair<double,double>
#define y1			yy1
#define eps      	(1e-9)
#define esit(a,b)  	( abs( (a)-(b) ) < eps )
#define sol(a)		( (a)<<1 )
#define sag(a)		( sol(a)|1 )
#define orta(a,b)	( ( (a)+(b) )>>1 )
#define mxn       	100005
using namespace std;

priority_queue< pii >q;
set<int>b;
set<int>::iterator it;

int n,na,nb;
int ta[mxn],tb[mxn];
int ar[mxn],mx;

void read(){
	freopen( "fabrica.in" , "r" , stdin );
	freopen( "fabrica.out" , "w" , stdout );

	scanf( "%d %d %d" , &n , &na , &nb );
	for( int i=1 ; i<=na ; i++ )	scanf( "%d" , ta+i );
	for( int i=1 ; i<=nb ; i++ )	scanf( "%d" , tb+i );

	return;
}

int check( int s ){

	int i,t;

	b.clear();
	for( i=1 ; i<=n ; i++ )	b.insert( ar[i] );

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

		t = s-tb[i];

		while( 1 ){

			it = b.upper_bound( t );
			if( it==b.begin() )	break;

			b.erase( --it );
			if( !b.size() )	return 1;

			t -= tb[i];

		}

	}

	return 0;

}

void solve(){

	int i,t,ind,bas,son,ort;

	read();

	for( i=1 ; i<=na ; i++ )	q.push( mp( -ta[i] , i ) );

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

		t = -q.top().st;
		ind = q.top().nd;
		q.pop();

		ar[i] = t;

		q.push( mp( -(t+ta[ind]),ind ) );

	}

	sort( tb+1,tb+nb+1 );

	bas = ar[n];
	son = 10000000;

	while( bas<son ){

		ort = orta(bas,son);

		if( check(ort) )	son = ort;
		else				bas = ort+1;

	}

	printf( "%d %d\n" , t , bas );

}

int main(){
	solve();
	return 0;
}