Pagini recente » Cod sursa (job #178654) | Cod sursa (job #2860199) | Cod sursa (job #2626150) | Cod sursa (job #1740357) | Cod sursa (job #2378753)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct dezmat{
int a,b;
}v[100002];
int d[100002];
const int L=30;
int n;
bool cmp(dezmat a,dezmat b){
return a.b<b.b;
}
int caut1(int x)
{
int r,pas;
r=0;
pas=1<<L;
while(pas!=0)
{
if(r+pas<=n && v[r+pas].b<=x)
r+=pas;
pas/=2;
}
return r;
}
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
fin>>v[i].a>>v[i].b;
sort(v+1,v+n+1,cmp);
int valoros;
for(int i=1; i<=n; i++)
{
valoros=v[i].b-v[i].a+d[caut1(v[i].a)];
d[i]=max(d[i-1],valoros);
}
int vmax=-1;
for(int i=1;i<=n;i++)
vmax=max(vmax,d[i]);
fout<<vmax;
return 0;
}