Cod sursa(job #1783391)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 18 octombrie 2016 23:11:14
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia3-programaredinamica1 Marime 0.71 kb
#include <cstdio>
#include <algorithm>
#define MAXN 100000
struct Timp{
   int a;
   int b;
};
Timp T[MAXN+1];
bool cmp(Timp x,Timp y){
   return x.b<y.b;
}
int dp[MAXN+1];
int main(){
   FILE*fi,*fout;
   int i,n,rez,pas;
   fi=fopen("heavymetal.in" ,"r");
   fout=fopen("heavymetal.out" ,"w");
   fscanf(fi,"%d " ,&n);
   for(i=1;i<=n;i++)
     fscanf(fi,"%d %d " ,&T[i].a,&T[i].b);
   std::sort(T+1,T+n+1,cmp);
   for(i=1;i<=n;i++){
      dp[i]=dp[i-1];
      rez=0;
      for(pas=1<<16;pas;pas>>=1)
        if(rez+pas<i&&T[rez+pas].b<=T[i].a)
          rez+=pas;
      if(dp[i]<dp[rez]+T[i].b-T[i].a)
        dp[i]=dp[rez]+T[i].b-T[i].a;
   }
   fprintf(fout,"%d" ,dp[n]);
   fclose(fi);
   fclose(fout);
   return 0;
}