Cod sursa(job #522212)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 14 ianuarie 2011 16:03:06
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct intz
{
	int st,dr;
};
bool ver(intz a,intz b)
{
	return(a.dr<b.dr);
}
intz s[100010];
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%d",&s[i].st,&s[i].dr);
	sort(s+1,s+n+1,ver);
	max=s[n].dr;
	for(i=1;i<=max;i++)
	{
		t[i]=t[i-1];
		while(s[last].dr==i)
		{
			if(t[i]<(t[s[last].st]+s[last].dr-s[last].st))
				t[i]=t[s[last].st]+s[last].dr-s[last].st;
			last++;
		}
	}
	printf("%d",t[max]);
	return 0;
}