Cod sursa(job #910578)

Utilizator superman_01Avramescu Cristian superman_01 Data 10 martie 2013 21:25:06
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 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,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;
}