Pagini recente » Cod sursa (job #2241399) | Cod sursa (job #1111193) | Cod sursa (job #2936395) | Cod sursa (job #283201) | Cod sursa (job #204341)
Cod sursa(job #204341)
using namespace std;
#include <cstdio>
#include <algorithm>
#define Nmax 100001
int N,i,i1,i2,nr,last;
int A[Nmax],B[Nmax],AA[Nmax],BB[Nmax],s1[Nmax],s2[Nmax], T[2*Nmax];
int cmp1(const int &a,const int &b)
{
return A[a]<A[b];
}
int cmp2(const int &a,const int &b)
{
return B[a]<B[b];
}
void citire()
{
freopen("heavymetal.in","r",stdin);
scanf("%d",&N);
for (i=0; i<N; ++i)
{
scanf("%d %d",&A[i],&B[i]);
s1[i] = s2[i] = i;
}
}
int main()
{
citire();
sort(s1,s1+N,cmp1);
sort(s2,s2+N,cmp2);
//normalizare
while (i1<N || i2<N)
{
if (i1 == N)
{
if (B[s2[i2]] == last) BB[s2[i2]] = nr;
else { last=B[s2[i2]]; BB[s2[i2]] = (++nr); }
++i2;
}
else
if (i2 == N)
{
if (A[s1[i1]] == last) AA[s1[i1]] = nr;
else { last=A[s1[i2]]; AA[s1[i1]] = (++nr); }
++i1;
}
else
if (A[s1[i1]]<B[s2[i2]])
{
if (A[s1[i1]] == last) AA[s1[i1]] = nr;
else { last=A[s1[i2]]; AA[s1[i1]] = (++nr); }
++i1;
}
else
{
if (B[s2[i2]] == last) BB[s2[i2]] = nr;
else { last=B[s2[i2]]; BB[s2[i2]] = (++nr); }
++i2;
}
}
//dinamica
for (i=0, i1=0; i<=nr; ++i)
{
T[i] = T[i-1];
while (BB[s2[i1]]==i)
{
T[i] = max(T[i], T[AA[s2[i1]]] + B[s2[i1]]-A[s2[i1]]);
++i1;
}
}
freopen("heavymetal.out","w",stdout);
printf("%d\n",T[nr]);
fclose(stdout);
return 0;
}