Pagini recente » Cod sursa (job #1152079) | Cod sursa (job #2000127) | Istoria paginii runda/cum_sa_fii_manelist | Cod sursa (job #1932714) | Cod sursa (job #1783391)
#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;
}