Pagini recente » Cod sursa (job #2470432) | Cod sursa (job #390083) | Cod sursa (job #1768528) | Cod sursa (job #1355552) | Cod sursa (job #1867054)
#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;
while(s<d)
{
med=(d+s)/2;
if(num[med].dr>num[current].st)
d=med-1;
else
s=med+1;
}
return med;
}
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;
}