Cod sursa(job #2118798)

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

const int N = 100001;
pair <int, int> v[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;
    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 ++ )
        {
            for ( j = i - 1 ; v[j].second > v[i].first && j > 0 ; j-- );
            d[i] = max ( (d[j] + lungime (i) ), d[i-1] );
        }
    fout << d[n];
    return 0;
}