Cod sursa(job #2118800)

Utilizator CryshanaGanea Carina Cryshana Data 31 ianuarie 2018 08:27:54
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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 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 ++ )
        {
            if ( p[i-1].second != v[i].first )
            {
                p[i].first = i;
                p[i].second = v[i].first;
            }
            else
            {
                p[i].first = p[i-1].first;
                p[i].second = p[i-1].second;
            }
            d[i] = max ( (d[p[i].first-1] + lungime (i) ), d[i-1] );
        }
    fout << d[n];
    return 0;
}