Pagini recente » Cod sursa (job #720519) | Cod sursa (job #1011785) | Cod sursa (job #290482) | Cod sursa (job #868831) | Cod sursa (job #855274)
Cod sursa(job #855274)
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>
#define DN 100005
#define mp make_pair
#define f first
#define s second
#define kind pair< pair<int,int> , int >
using namespace std;
int best[DN],normal[2*DN],n;
kind v[DN];
set<int> s;
set<int>::iterator it;
int caut_bin(int x)
{
int left=1,right=n,mij,rez=0;
while(left<=right)
{
mij=(left+right)/2;
if( x <= v[mij].f.s)
{
rez=mij;
right=mij-1;
}
else
left=mij+1;
}
return rez;
}
void normalizare()
{
int i=0;
for(it=s.begin();it!=s.end();++it)
normal[*it]=++i;
}
struct cmp
{
bool operator()(const kind &a,const kind &b)const
{
if(a.f.s == b.f.s)
return a.f.f < b.f.f;
else
return a.f.s < b.f.s ;
}
};
int main()
{
int tmax=0;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f>>n;
for(int i=1;i<=n;++i)
{
int x,y;
f>>x>>y;
s.insert(x);
s.insert(y);
v[i]=mp( mp(x,y) , y-x ) ;
}
normalizare();
for(int i=1;i<=n;++i)
{
v[i].f.f=normal[v[i].f.f];
v[i].f.s=normal[v[i].f.s];
tmax=max(tmax,v[i].f.s);
}
sort(v+1,v+n+1,cmp());
// for(int i=1;i<=n;++i)
// cout<<v[i].f.f<<" "<<v[i].f.s<<endl;
for(int i=1;i<=tmax;++i)
{
best[i]=best[i-1];
int j=caut_bin(i)-1;
while( v[++j].f.s == i && j<=n)
best[i]= max ( best [i] , best [ v[j].f.f ] + v[j].s );
}
g<<best[tmax];
return 0;
}