Pagini recente » Cod sursa (job #1439053) | Cod sursa (job #3280878) | Cod sursa (job #2198647) | Cod sursa (job #2422379) | Cod sursa (job #910590)
Cod sursa(job #910590)
#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].second,&v[i].first);
fclose(f);
}
int bs( int left,int right,int val )
{
int mid,pos;
while( left <= right )
{
mid=(left+right)/2;
if(v[mid].first<= 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].first-v[1].second;
for(int i(2); i <= N ; ++i)
{
int poz=bs(1,i-1,v[i].second);
DP[i]=max(DP[i-1],DP[poz]+(v[i].first-v[i].second));
}
}
void write ( void )
{
fprintf(g,"%d",DP[N]);
fclose(g);
}
int main( void )
{
read();
solve();
write();
return 0;
}