Cod sursa(job #1151355)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 24 martie 2014 08:32:49
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 100005

using namespace std;

struct nr
{
    int a,b;
    bool operator <(const nr &A) const
    {
        return b<A.b;
    }
};
nr v[Nmax];
int t[Nmax],dp[Nmax];

int main()
{
    int i,N,ind=0;
    freopen ("heavymetal.in","r",stdin);
    freopen ("heavymetal.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<=N;++i)
        scanf("%d%d", &v[i].a,&v[i].b);
    sort(v+1,v+N+1);
    for(i=1;i<=N;++i)
    {
        while(ind<N && v[ind+1].b<=v[i].a)
            ++ind;
        t[i]=ind;
    }
    for(i=1;i<=N;++i)
        dp[i]=max(dp[i-1],dp[t[i]]+v[i].b-v[i].a);

    printf("%d\n", dp[N]);
    return 0;
}