Pagini recente » Cod sursa (job #1258156) | Cod sursa (job #1419997) | Cod sursa (job #2725897) | Cod sursa (job #1771519) | Cod sursa (job #520176)
Cod sursa(job #520176)
# 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;}
};
struct str{
int v, i, t;
str(){}
str(int V, int I, int T){
v=V;i=I;t=T;}
};
int n, b[DIM], p[2*DIM], tmp;
nod v[DIM];
str w[DIM];
bool inline cmp(int i, int j)
{
if (w[i].v<w[j].v)return true;
return false;
}
bool inline comp (int i, int j)
{
if (v[i].b<v[j].b)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);
w[2*i-1]=str(a, i, 0);
w[2*i]=str(b, i, 1);
p[2*i-1]=2*i-1;
p[2*i]=2*i;
}
sort(p+1, p+2*n+1, cmp);
for(int i=1;i<=2*n;++i)
{
if (w[p[i]].v!=w[p[i-1]].v)
++tmp;
if (w[p[i]].t)
v[w[p[i]].i].y=tmp;
else
v[w[p[i]].i].x=tmp;
}
for(int i=1;i<=n;++i)
p[i]=i;
sort(p+1, p+n+1, comp);
}
int main ()
{
read ();
int u=v[p[1]].y;
for(int i=1;i<=n;++i)
{
for(int j=u+1;j<v[p[i]].y;++j)
b[j]=b[j-1];
b[v[p[i]].y]=max(b[v[p[i]].y],b[v[p[i]].y-1]);
b[v[p[i]].y]=max(b[v[p[i]].y],b[v[p[i]].x]+v[p[i]].b-v[p[i]].a);
u=v[p[i]].y;
}
ofstream fout ("heavymetal.out");
fout<<b[tmp];
return 0;
}