Pagini recente » Cod sursa (job #896098) | Cod sursa (job #50819) | Cod sursa (job #512780) | Cod sursa (job #1050737) | Cod sursa (job #1867116)
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
struct numere
{
int st;
int dr;
} num[nmax];
int n;
int dinamica[nmax];
bool cmp(numere a, numere b)
{
if(a.dr==b.dr)
return a.st<b.st;
return a.dr<b.dr;
}
int find_k(int s, int d, int current)
{
int med;
int raspuns;
int maxim=0;
while(s<=d)
{
med=(s+d)/2;
if(num[med].dr>num[current].st)
d=med-1;
else
{
s=med+1;
if(dinamica[med]>maxim)
raspuns=med;
}
}
return raspuns;
}
void citire()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
int s, d;
scanf("%d%d", &s, &d);
num[i].st=s;
num[i].dr=d;
}
}
void rezolvare()
{
sort(num+1, num+n+1, cmp);
dinamica[1]=num[1].dr-num[1].st;
for(int i=2; i<=n; i++)
{
int k;
k=find_k(1, n, i);
dinamica[i]=max(dinamica[i-1], num[i].dr-num[i].st+dinamica[k]);
}
}
void afisare()
{
printf("%d\n", dinamica[n]);
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
citire();
rezolvare();
afisare();
return 0;
}