Cod sursa(job #1874005)

Utilizator FredyLup Lucia Fredy Data 9 februarie 2017 16:27:18
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#define nmax 100010

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

struct element{int st,dr;} v[nmax];
int n,i,j;
int best[nmax];

bool cmp(element a,element b)
{
    if(a.dr!=b.dr) return a.dr<b.dr;
    return a.st<b.st;
}

int search(int x)
{
    int left=0,right=n,mid;
    while (left<=right)
    {
        mid=(left+right)/2;
        if(v[mid].dr<=x) left=mid+1;
        else right=mid-1;
    }
    return right;
}


int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>v[i].st>>v[i].dr;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;++i)
    {
        j=search(v[i].st);
        best[i]=max(best[i-1],v[i].dr-v[i].st+best[j]);
    }
    fout<<best[n];
    return 0;
}