Cod sursa(job #1471526)

Utilizator Liviu98Dinca Liviu Liviu98 Data 14 august 2015 11:32:57
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define NMax 100002
using namespace std;
int A[NMax],B[NMax],Best[NMax];
int TMax;
struct Interval
{
    int x,y;
}V[NMax];

struct cmp
{
    bool operator () (Interval a, Interval b) const
    {
        return a.y < b.y;
    }
};

int main()
{
    int N,x,y,sol;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%d%d",&V[i].x,&V[i].y);
    }

    sort(V+1,V+N+1,cmp());

    Best[1]=V[1].y-V[1].x;
    sol=Best[1];

    for(int i=2;i<=N;i++)
    {
        Best[i]=Best[i-1];
        int s=1;
        int d=i-1;
        int j=0;
        while(s<=d)
        {
            int mij=(s+d)/2;
            if(V[mij].y<=V[i].x)
            {
                j=mij;
                s=mij+1;
            }
            else
                d=mij-1;
        }
            Best[i]=max(Best[i],Best[j]+V[i].y-V[i].x);
            sol=max(sol,Best[i]);
    }
    printf("%d",sol);
}