Cod sursa(job #160356)

Utilizator sraduvictorSarmasag Radu Victor sraduvictor Data 15 martie 2008 10:52:52
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
//pentru i de la 1 la Tmax   
//    Best[i] = Best[i-1];   
//    pentru fiecare concert j cu B[j] = i   
//        Best[i] = max(Best[i], Best[A[j]] + (B[j] - A[j]))
/*
Solutia ce ar fi obtinut punctajul maxim nu reprezinta nimic 
altceva decat o rafinare a acestui algoritm. Observam ca valorile A[i] si B[i] 
sunt foarte mari, iar pentru a rezolva aceasta problema le vom normaliza. 
Vom sorta intervalele in functie de timpul de terminare si vom calcula Best[i] 
doar pentru valorile in care exista cel putin un concert care se termina la timpul i.
*/
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

class Pair
{
public:
	int a, b;
	Pair( int a, int b )
	{
		this->a = a;
		this->b = b;
	}
	bool operator < ( const Pair p ) const
	{
		return b < p.b;
	}
};

int main( int argc, char *argv[] )
{
	vector<Pair> interv;
	vector<int> best;
	int n;
	
	FILE *fin = fopen( "heavymetal.in", "r" );
	fscanf( fin, "%d", &n );
	for ( int i = 0; i < n; i++ )
	{
		int a, b;
		fscanf( fin, "%d %d", &a, &b );
		interv.push_back( Pair( a, b ) );
		best.push_back( 0 );
	}
	fclose( fin );
	sort( interv.begin(), interv.end() );
	
	int max = 0;
	
	for ( int i = 0; i < n; i++ )
	{
		int j = i-1;
		while ( j >= 0 && interv[j].b > interv[i].a ) j--;
		if ( j == -1 )
			best[i] = max( best[i], interv[i].b - interv[i].a );
		else
			best[i] = max( best[i], interv[i].b - interv[i].a + best[j] );
		if ( max < best[i] )
			max = best[i];
	}
	
	FILE *fout = fopen( "heavymetal.out", "w" );
	fprintf( fout, "%d\n", max );
	fclose( fout );

	return 0;
}