Pagini recente » Cod sursa (job #2102713) | Cod sursa (job #2372892) | Cod sursa (job #2530566) | Cod sursa (job #2036649) | Cod sursa (job #1783333)
#include <cstdio>
#include <algorithm>
#define MAXN 100000
int d[MAXN+1];
struct aa{
int ind, c, sd, cost;
}v[2*MAXN+1];
struct irt{
int st, dr, cost;
}a[MAXN+1];
inline int maxim(int a, int b){
return (a > b ? a : b);
}
bool cmp(const aa &a, const aa &b){
return (a.c < b.c);
}
bool cmp2(const irt &a, const irt &b){
return (a.dr < b.dr);
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int k=0, n, i, x, y, t=0;
scanf("%d", &n);
for(i=1; i<=n; ++i)
{
scanf("%d%d", &x, &y);
v[++k].ind = i;
v[k].c = x;
v[k].sd = 0;
v[++k].ind = i;
v[k].c = y;
v[k].sd = 1;
v[k].cost = y-x+1;
}
std::sort(v+1, v+k+1, cmp);
for(i=1; i<=k; ++i)
{
if(v[i].c > v[i-1].c)
{
t++;
v[i].c = t;
}else v[i].c = v[i-1].c;
if(v[i].sd == 0)
a[v[i].ind].st = v[i].c;
else
{
a[v[i].ind].dr = v[i].c;
a[v[i].ind].cost = v[i].cost;
}
}
std::sort(a+1, a+n+1, cmp2);
for(i=1; i<=n; ++i)
{
x = a[i].dr;
d[x] = maxim(d[x], maxim(d[x-1], d[x-a[i].st+1] + a[i].cost));
}
printf("%d", d[a[n].dr]);
return 0;
}