Cod sursa(job #2628804)

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

using namespace std;

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

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

bool Comp(time a,time b){
    return a.f<b.f;
}

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,Comp);

    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;
}