Cod sursa(job #1366215)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 28 februarie 2015 20:53:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<stdio.h>
//ce faci mihnea?
//poate e n log n
long int n,i,j,k,a[100002],b[100002],aux,max[100002];
void sh(long int i1,long int i2)
{
    aux=a[i1];
    a[i1]=a[i2];
    a[i2]=aux;
    aux=b[i1];
    b[i1]=b[i2];
    b[i2]=aux;
}
void hd(long int ic,long int nc)
{
    long int is,is1;
    is=2*ic;is1=2*ic+1;
    if(is>nc)return;
    if(is<nc)if(b[is1]>b[is])is=is1;
    if(b[is]>b[ic])
    {
        sh(is,ic);
        hd(is,nc) ;
    }
}
long int cauta(long int st,long int dr)
{
    long int mid;
    mid=(st+dr)/2;
    if(mid==st) return mid;
    if(b[mid]<=a[i]) return cauta(mid,dr);
    return cauta(st,mid);
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    fscanf(fin,"%ld",&n);
    for(i=1;i<=n;i++) fscanf(fin,"%ld%ld",&a[i],&b[i]);
    for(i=n/2;i>=1;i--) hd(i,n);
    for(i=n;i>=1;i--)
    {
        sh(1,i);
        hd(1,i-1);
    }
    for(i=1;i<=n;i++)
    {
        j=cauta(0,i);
        max[i]=(max[i-1]>max[j]+b[i]-a[i])?max[i-1]:max[j]+b[i]-a[i];
    }
    fprintf(fout,"%ld\n",max[n]);
    fclose(fin);
    fclose(fout);
    return 0;
}