Pagini recente » Cod sursa (job #4684) | Borderou de evaluare (job #2981567) | Cod sursa (job #566736) | Cod sursa (job #3195558) | Cod sursa (job #784689)
Cod sursa(job #784689)
# include <fstream>
# include <iostream>
# include <algorithm>
# define DIM 100003
# define max(a,b) a>b?a:b
using namespace std;
struct nod{
int a, b, x, y;
nod(){}
nod(int A, int B, int X, int Y){
a=A;b=B;x=X;y=Y;}
};
int n, B[2*DIM], p[2*DIM], tmp;
nod v[DIM];
bool inline cmp(int i, int j)
{
if (i%2)i=v[i/2].a;
else i=v[i/2].b;
if (j%2)j=v[j/2].a;
else j=v[j/2].b;
if (i<j)return true;
return false;
}
void read ()
{
ifstream fin ("heavymetal.in");
fin>>n;
int a, b;
for(int i=1;i<=n;++i)
{
fin>>a>>b;
v[i]=nod(a, b, 0, 0);
p[2*i-1]=2*i-1;
p[2*i]=2*i;
}
sort(p+1, p+2*n+1, cmp);
}
void solve ()
{
int u=0, a, b;
for(int i=1;i<=2*n;++i)
{
if (p[i]%2)a=v[p[i]/2].a;
else a=v[p[i]/2].b;
if ((p[i-1])%2)b=v[(p[i-1])/2].a;
else b=v[(p[i-1])/2].b;
if (a!=b)++tmp;
if (p[i]%2)
v[p[i]/2].x=tmp;
else
{
v[p[i]/2].y=tmp;
for(int j=u+1;j<tmp;++j)
B[j]=B[j-1];
B[tmp]=max(B[tmp-1],B[tmp]);
B[tmp]=max(B[tmp],B[v[p[i]/2].x]+v[p[i]/2].b-v[p[i]/2].a);
u=tmp;
}
}
}
int main ()
{
read ();
solve ();
ofstream fout ("heavymetal.out");
fout<<B[tmp];
return 0;
}