Cod sursa(job #2628805)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 17 iunie 2020 16:35:46
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int n,i,k;
int x[100003];

struct time{
    int s,f;
}v[100003];


int Bin(int a,int st,int dr){
    int Max=0;

    while(st<=dr){
        int m=(st+dr)/2;

        if(v[m].f<=a)
            Max=m,
            st=m+1;
        else
            dr=m-1;
    }

    return Max;

}

int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);

    scanf("%d",&n);

    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].s,&v[i].f);

    sort(v+1,v+n+1);
    reverse(v+1,v+n+1);

    x[1]=v[1].f-v[1].s;
    for(i=2;i<=n;i++){
        k=Bin(v[i].s,1,i-1);
        x[i]=max(x[i-1],x[k]+v[i].f-v[i].s);
    }

    printf("%d",x[n]);

    return 0;
}