Pagini recente » Istoria paginii runda/emag_2016-incepatori-4 | Cod sursa (job #403732) | Cod sursa (job #1309214) | Cod sursa (job #2742785) | Cod sursa (job #2054553)
#include <iostream>
#include <cstdio>
#include <algorithm>
#define max(a, b) a>b?a:b
#define N 100005
using namespace std;
int n, ind[N], din[N];
struct timp
{
int st, fin, dur;
}a[N];
void citire()
{
scanf("%d\n", &n);
for(int i=1;i<=n;i++)
scanf("%d %d\n", &a[i].st, &a[i].fin), a[i].dur=a[i].fin-a[i].st, ind[i]=i;
}
void sortare(int ind[], int st, int dr)
{
int i=st, j=dr;
int pivot=ind[(st+dr)/2];
while(i<=j)
{
while(a[ind[i]].st<a[pivot].st)
i++;
while(a[ind[j]].st>a[pivot].st)
j--;
if(i<=j)
{
int aux=ind[i];
ind[i]=ind[j];
ind[j]=aux;
i++;
j--;
}
}
if(st<j)
sortare(ind, st, j);
if(i<dr)
sortare(ind, i, dr);
}
int caut(int x, int st, int dr)
{
if(a[ind[st]].fin==x)
return ind[st];
int mij=(st+dr)/2;
if(x>a[ind[mij]].fin)
return caut(x, mij+1, dr);
return caut(x, st, mij);
}
void calcul()
{
for(int i=1;i<=a[ind[n]].fin;i++)
{
din[i]=din[i-1];
for(int j=1;j<=n;j++)
if(a[ind[j]].fin==i)
din[i]=max(din[i], din[a[ind[j]].st]+a[ind[j]].dur);
else
if(a[ind[j]].fin>i)
break;
}
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
citire();
sortare(ind, 1, n);
calcul();
printf("%d", din[a[ind[n]].fin]);
return 0;
}