Pagini recente » Cod sursa (job #1566916) | Cod sursa (job #1145439) | Cod sursa (job #1885282) | Cod sursa (job #1901116) | Cod sursa (job #1867002)
#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(numere x[nmax], int s, int start)
{
int i;
for(i=start;i<n&&x[i+1].dr<s;i++);
return i;
}
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;
int last_k=1;
for(int i=1;i<=n;i++)
{
int k;
k=find_k(num, num[i].st, last_k);
last_k=k;
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;
}