Pagini recente » Cod sursa (job #2147638) | Cod sursa (job #1161392) | Cod sursa (job #1020319) | Cod sursa (job #2742762) | Cod sursa (job #910619)
Cod sursa(job #910619)
#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;
}