Cod sursa(job #160357)

Utilizator sraduvictorSarmasag Radu Victor sraduvictor Data 15 martie 2008 11:07:37
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 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, index;
	Pair( int a, int b )
	{
		this->a = a;
		this->b = b;
		index = 0;
	}
	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;
	int nr = 0;
	
	for ( int i = 0; i < n; i++ )
	{
		if ( i > 0 && interv[i].b > interv[i-1].b ) nr++;
		interv[i].index = nr;
	
		int j = i-1;
		while ( j >= 0 && interv[j].b > interv[i].a ) j--;
		
		if ( j == -1 )
		{
			if ( best[interv[i].index] < interv[i].b - interv[i].a )
				best[interv[i].index] = interv[i].b - interv[i].a;
		}
		else if ( best[interv[i].index] < best[interv[j].index] + interv[i].b + interv[i].a )
			best[interv[i].index] = interv[i].b - interv[i].a + best[interv[j].index];
		if ( max < best[interv[i].index] )
			max = best[interv[i].index];
	}
	
	FILE *fout = fopen( "heavymetal.out", "w" );
	fprintf( fout, "%d\n", max );
	fclose( fout );

	return 0;
}