Cod sursa(job #910619)

Utilizator superman_01Avramescu Cristian superman_01 Data 10 martie 2013 21:53:41
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstdio>
#include<algorithm>
#include<vector>
 
#define MAX_SIZE 100005
 
 
FILE *f=fopen("heavymetal.in","r");
FILE *g=fopen("heavymetal.out","w");
 
using namespace std;
 
pair<int,int> v[MAX_SIZE];
int N;
long long DP[MAX_SIZE];
 
void read ( void )
{
   fscanf(f,"%d",&N);
   for(int i(1); i <= N ; ++i )
    fscanf(f,"%d%d",&v[i].first,&v[i].second);
 
   fclose(f);
 
 
}
int bs( int left,int right,int val )
{
 
    int mid,pos;
    while( left <= right )
    {
        mid=(left+right)/2;
        if(v[mid].second <= val )
         {
             left=mid+1;
             pos=mid;
         }
         else
            right=mid-1;
 
 
    }
    return pos;
 
 
}
void solve ( void )
{
   sort(v+1,v+N+1);
   DP[1]=v[1].second-v[1].first;
   for(int i(2); i <= N ; ++i)
   {
      int poz=bs(1,i-1,v[i].first);
      DP[i]=max(DP[i-1],DP[poz]+(v[i].second-v[i].first));
   }
 
 
}
 
void write ( void )
{
    fprintf(g,"%d",DP[N]);
    fclose(g);
 
}
 
int main( void )
{
    read();
    solve();
    write();
    return 0;
}