Cod sursa(job #2118806)

Utilizator CryshanaGanea Carina Cryshana Data 31 ianuarie 2018 08:54:00
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <cstring>
#include <algorithm>
#include <fstream>
using namespace std;

const int N = 100001;
pair <int, int> v[N], p[N];
long long d[N] ;

bool comp ( pair <int,int> a, pair <int, int> b)
{
    if ( a.second < b.second)
    return 1;

    else
    {
        if ( a.second == b.second && a.first < b.first )
            return 1;

        else
            return 0;
    }
}

inline int lungime ( int a )
{
    return v[a].second - v[a].first;
}

int caut_bin ( int a , int n)
{
    int pas = 1 << 17, r = 0;
    while ( pas != 0 )
    {
        if ( r + pas <= n && v[r + pas].second <= a )
            r += pas;
        pas = pas >> 1;
    }
    return r;
}

int main()
{
    ifstream fin ("heavymetal.in");
    ofstream fout ("heavymetal.out");
    int n, j, m = 0;
    fin >> n;

    for ( int i = 1 ; i <= n ; i ++ )
    fin >> v[i].first >> v[i].second;

    sort ( v + 1 , v + 1 + n, comp );

    for ( int i = 1 ; i <= n ; i ++ )
        {
            d[i] = max ( (d[caut_bin( v[i].first, n )] + lungime (i) ), d[i-1] );
        }
    fout << d[n];
    return 0;
}