Pagini recente » Cod sursa (job #1747094) | Cod sursa (job #3287807) | Cod sursa (job #2692963) | Cod sursa (job #373850) | Cod sursa (job #522222)
Cod sursa(job #522222)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct interval
{
int x,y;
};
interval f[100010];
bool cmp(interval a,interval b)
{
return a.y<b.y;
}
int t[100010];
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,last=1,max;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&f[i].x);
scanf("%d",&f[i].y);
}
sort(f+1,f+n+1,cmp);
max=f[n].y;
for(i=1;i<=max;i++)
{
t[i]=t[i-1];
while(f[last].y==i)
{
if(t[i]<t[f[last].x]+i-f[last].x)
t[i]=t[f[last].x]+i-f[last].x;
last++;
}
}
printf("%d",t[max]);
return 0;
}