Pagini recente » Clasament dupa rating | Istoria paginii runda/lasm_baraj1_cl11/clasament | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #522069)
Cod sursa(job #522069)
#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
};
point a1[100002];
int t[1000002];
bool comp(point a,point b)
{
return a.y<b.y;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,p;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&a1[i].x,&a1[i].y);
sort(a1+1,a1+n+1,comp);
t[a1[1].y]=a1[1].y-a1[1].x;
p=2;
for(i=a1[1].y+1;i<=a1[n].y;i++)
{
t[i]=t[i-1];
if (i==a1[p].y)
{
for(;p<=n&& a1[p].y==i;p++)
{
if(t[i]<t[a1[p].x]+i-a1[p].x)
{
t[i]=t[a1[p].x]+i-a1[p].x;
}
}
}
}
printf("%d",t[a1[n].y]);
return 0;
}