Cod sursa(job #1783464)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 19 octombrie 2016 00:29:36
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia3-programaredinamica1 Marime 0.93 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2000000000
#define MaxN 100005
using namespace std;
     
FILE *IN,*OUT;
int N,D[MaxN],P[MaxN];
struct _Interval
{
    int x,y;
}v[MaxN];
bool cond(int a,int b)
{
    return v[a].y<v[b].y||(v[a].y==v[b].y&&v[a].x<v[b].x);
}
int Binary_Search(int val)
{
    int hi=N,lw=1,mid,last=0;
    while(lw<=hi)
    {
        mid=(lw+hi)>>1;
        if(v[P[mid]].y<=val)
            last=mid,lw=mid+1;
        else hi=mid-1;
    }
    return last;
}
int main()
{
    IN=fopen("heavymetal.in","r");
    OUT=fopen("heavymetal.out","w");
     
    fscanf(IN,"%d",&N);
    for(int i=1;i<=N;i++)
    {
        fscanf(IN,"%d%d",&v[i].x,&v[i].y);
        P[i]=i;
    }
    sort(P+1,P+1+N,cond);
    for(int i=1;i<=N;i++)
        D[i]=max(D[i-1],D[Binary_Search(v[P[i]].x)]+v[P[i]].y-v[P[i]].x);
    fprintf(OUT,"%d",D[N]);
    return 0;
}