Cod sursa(job #1791048)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 28 octombrie 2016 23:58:09
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
struct gogu
{
    int x,y;
}v[100001];
int rez[100001];
int max(int a,int b)
{
    if(a>b) return a;
    return b;
}
bool comp(gogu a,gogu b)
{
    return a.y<b.y;
}
int cautbin(int x,int n)
{
    int i=0,pas=1<<16;
    while(pas)
    {
        if(i+pas<=n && v[i+pas].y<=x)
            i+=pas;
        pas/=2;
    }
    return i;
}
int main()
{
    int i,n,x;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,comp);
    for(i=1; i<=n; i++)
    {
        x=cautbin(v[i].x,i-1);
        rez[i]=max(rez[i-1],rez[x]+v[i].y-v[i].x);
    }
    printf("%d\n",rez[n]);

    return 0;
}