Pagini recente » Cod sursa (job #494972) | Cod sursa (job #1648653) | Cod sursa (job #1894753) | Cod sursa (job #2542884) | Cod sursa (job #1061255)
#include <fstream>
#include <algorithm>
using namespace std;
int v[200005],best[100005];
int n,i,st,dr,val,mid,k,tmax,j;
struct data{
int a;
int b;
int vec;
}s[100005];
bool cmp(const data &s1, const data &s2){
if(s1.b<s2.b)
return 1;
else
return (s1.a<s1.a);
}
int main(){
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f>>n;
for(i=1;i<=n;i++){
k++;
f>>s[i].a;
v[k]=s[i].a;
k++;
f>>s[i].b;
v[k]=s[i].b;
s[i].vec=s[i].b-s[i].a;
}
sort(v+1,v+k+1);
for(i=1;i<=n;i++){
val=s[i].a;
st=1;dr=k;
while(st<=dr){
mid=(st+dr)/2;
if(v[mid]<val)
st=mid+1;
else
dr=mid-1;
}
s[i].a=st;
val=s[i].b;
st=1;dr=k;
while(st<=dr){
mid=(st+dr)/2;
if(v[mid]<val)
st=mid+1;
else
dr=mid-1;
}
s[i].b=st;
if(s[i].b>tmax)
tmax=s[i].b;
}
sort(s+1,s+n+1,cmp);
for(i=1;i<=tmax;i++){
best[i]=best[i-1];
st=1;dr=n;
while(st<=dr){
mid=(st+dr)/2;
if(s[mid].b<i)
st=mid+1;
else
dr=mid-1;
}
for(j=st;s[j].b==i;j++){
if(best[i]<best[s[j].a]+(s[j].vec))
best[i]=best[s[j].a]+(s[j].vec);
}
}
g<<best[tmax]<<"\n";
/*for(i=1;i<=n;i++)
g<<s[i].a<<" "<<s[i].b<<"\n";*/
f.close();g.close();
return 0;
}