Cod sursa(job #1852795)

Utilizator nnnmmmcioltan alex nnnmmm Data 21 ianuarie 2017 10:39:22
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>

struct interval
{
 int in,sf;
};

const int NMAX=100001;

interval v[NMAX+1];

bool cmp(interval a,interval b)
{
 if(a.sf==b.sf)
    return a.in<b.in;
 return a.sf<=b.sf;
}

int Search(int val,int in,int sf)
{
 int st=in,dr=sf;
 int rasp=0;
 while(st<=dr)
       {
        int mij=(st+dr)/2;
        if(v[mij].sf>val)
           {
            dr=mij-1;
           }
        else
           {
            rasp=mij;
            st=mij+1;
           }
       }
 return rasp;
}

int d[NMAX+1];

int main()
{
 FILE *in=fopen("heavymetal.in","r");
 int n;
 fscanf(in,"%d ",&n);
 for(int i=1;i<=n;i++)
     {
      fscanf(in,"%d %d ",&v[i].in,&v[i].sf);
     }
 fclose(in);
 std::sort(v+1,v+n+1,cmp);
 for(int i=1;i<=n;i++)
     {
      int st=Search(v[i].in,1,i),dr=i;
      d[i]=std::max(d[i-1],d[st]+(v[i].sf-v[i].in));
     }
 FILE *out=fopen("heavymetal.out","w");
 fprintf(out,"%d\n",d[n]);
 fclose(out);
 return 0;
}