Cod sursa(job #1294996)

Utilizator Miruna_DMiruna Miruna_D Data 18 decembrie 2014 17:14:19
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#define Nmax 1000001
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int n,DP[Nmax];
pair <int,int> interval[Nmax];
int k;
void read()
{
    fin>>n;
    int i;
    for(i=1;i<=n;i++)
    {
        int x,y;
        fin>>x>>y;
        interval[++k]=make_pair(x,y);
    }
}

int Search(int poz)
{
    int s=1,d,m;
    d=poz;
    while(s<=d)
    {
        m=(s+d)/2;
        if(interval[m].second<=interval[poz].first)
            s=m+1;
        else d=m-1;
    }
    m=(s+d)/2;
    if(m && interval[m].second>interval[poz].first) m--;
    return m;

}


int main()
{
    read();
    sort(interval+1,interval+n+1);
    int i;

    for(i=1;i<=n;i++)
        DP[i]=max(DP[i-1], DP[Search(i)]+interval[i].second-interval[i].first);

    fout<<DP[n];
    return 0;
}