Cod sursa(job #1990244)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 11 iunie 2017 00:00:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,i,j,x,y,t,d[1000003];
pair <int, int> v[100003];

bool cmp(pair <int, int> a, pair <int, int> b)
{
    return a.second < b.second;
}

int main()
{
    int l, n, i;
    l = 1;
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> v[i].first >> v[i].second;
    sort (v+1, v+n+1, cmp);
    for (i=1; i<=v[n].second; i++)
    {
        d[i] = d[i-1];
        while (v[l].second == i)
        {
            d[i] = max(d[i], d[v[l].first]+i-v[l].first);
            l++;
        }
    }
    fout << d[v[n].second] << "\n";
    return 0;
}