Pagini recente » Cod sursa (job #1133715) | Cod sursa (job #2484419) | Cod sursa (job #1189781) | Cod sursa (job #930341) | Cod sursa (job #160357)
Cod sursa(job #160357)
//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;
}