Cod sursa(job #1295667)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 19 decembrie 2014 22:55:23
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 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,sol=0;
    d=poz-1;
    while(s<=d)
    {
        m=(s+d)/2;
        if(interval[m].second<=interval[poz].first)
        {    
	s=m+1;sol=m;}
        else d=m-1;
    }

    return sol;
 
}
 
 
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;
}