Cod sursa(job #522222)

Utilizator vlad_jp95Tarachiu Vlad vlad_jp95 Data 14 ianuarie 2011 16:22:41
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#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;
}