Pagini recente » Cod sursa (job #3255817) | Cod sursa (job #1214723) | Cod sursa (job #2798911) | Cod sursa (job #2829082) | Cod sursa (job #1857094)
#include<fstream>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct spec
{
int inc,sf;
};
spec v[100001];
int n,sol[100001];
int bs(int x)
{
int pas = 1<<16,i=0,j;
while(pas)
{
if(i+pas<=n && v[i+pas].sf<=v[x].inc)
i+=pas;
pas/=2;
}
return i;
}
void schimb(spec &a,spec &b)
{
spec aux;
aux=a;
a=b;
b=aux;
}
int partitie(int st,int dr)
{
int i,j;
j=st;
for(i=st;i<dr;i++)
{
if(v[i].sf<v[dr].sf)
schimb(v[j++],v[i]);
}
schimb(v[j],v[dr]);
return j;
}
void qsort(int st,int dr)
{
if(st>=dr)
return;
int p=partitie(st,dr);
qsort(st,p-1);
qsort(p+1,dr);
}
int maxim(int a,int b)
{
if(a>b)
return a;
return b;
}
int main()
{
int i,maxx=0,j;
f>>n;
for(i=1;i<=n;i++)
f>>v[i].inc>>v[i].sf;
qsort(1,n);
for(i=1;i<=n;i++)
if(v[i].sf - v[i].inc > maxx)
{
maxx = v[i].sf - v[i].inc;
sol[i] = maxx;
}
else
sol[i] = maxx;
for(i=2;i<=n;i++)
{
j = bs(i);
sol[i] = maxim(sol[i-1], sol[j] + (v[i].sf - v[i].inc));
}
g<<sol[n];
return 0;
}