Cod sursa(job #1729663)

Utilizator borcanirobertBorcani Robert borcanirobert Data 15 iulie 2016 13:49:10
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

const int MAX = 100005;
struct Interval{
    int x, y;
};
Interval a[MAX];
int D[MAX];
int N;

void Read();
void Solve();
int CautareBinara( int x );

bool Comp( const Interval& a, const Interval& b )
{
    if ( a.y < b.y || ( a.y == b.y && a.x < b.x ) )
        return true;
    return false;
}

int main()
{
    Read();
    Solve();

    fout << D[N] << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i;

    fin >> N;
    for ( i = 1; i <= N; i++ )
    {
        fin >> a[i].x >> a[i].y;
    }

    sort( a + 1, a + 1 + N, Comp );
}

void Solve()
{
    int i, j;

    D[1] = a[1].y - a[1].x;
    for ( i = 2; i <= N; i++ )
        D[i] = max( D[CautareBinara(i)] + ( a[i].y - a[i].x ), D[i - 1] );
}

int CautareBinara( int x )
{
    int st = 1, dr = x - 1, mid;
    int p = 0;

    while ( st <= dr )
    {
        mid = ( st + dr ) / 2;

        if ( a[mid].y <= a[x].x )
        {
            p = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }

    return p;
}