Cod sursa(job #1753930)

Utilizator enouGhAbu Ras Mohamed Ata Radu enouGh Data 7 septembrie 2016 12:34:56
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<bits/stdc++.h>
using namespace std;
struct comparator
{
    bool operator()(const pair<int,int> &left,const pair<int,int> &right)
    {
        return left.second < right.second;
    }
};

int n,DP[100010],j;
pair<int , int >v[100010];
int main()
{
    ifstream in("heavymetal.in");
    ofstream out("heavymetal.out");
    in>>n;
    for(int i = 1; i <= n; i++)
        in>>v[i].first>>v[i].second;
    sort(v+1 , v+n+1 ,comparator());
    /*for(int i = 1; i<= n; i++)
        cout<<v[i].first<<" "<<v[i].second;*/
    j=1;
    for(int i = 1 ; i <= v[n].second ; i++)
    {
        DP[i] = DP [i-1];
        while( v[j].second == i )
            DP[i] = max(DP[i] , DP[ v[j].first ] + v[j].second - v[j].first ),j++;
    }
    out<<DP[v[n].second];
    return 0;
}