Cod sursa(job #1972154)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 22 aprilie 2017 11:15:00
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct SUPER
{
    int a,b;
};
int ans[1000005];
SUPER v[100005];
int cmp(SUPER x,SUPER y)
{
    if(x.b<y.b)
        return 1;
    if(x.b>y.b)
        return 0;
    if(x.a<y.a)
        return 1;
    return 0;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,i,x,j=0,aux;
    scanf("%d",&n);
    for(i=0; i<n; ++i)
        scanf("%d%d",&v[i].a,&v[i].b);
    sort(v,v+n,cmp);
    x=v[n-1].b;
    for(i=1; i<=x; ++i)
    {
        ans[i]=ans[i-1];
        while(i==v[j].b)
        {
            aux=ans[v[j].a]+v[j].b-v[j].a;
            if(aux>ans[i])
                ans[i]=aux;
            j++;
        }
    }
    printf("%d\n",ans[x]);
    return 0;
}