Cod sursa(job #522238)

Utilizator vlad_jp95Tarachiu Vlad vlad_jp95 Data 14 ianuarie 2011 17:02:47
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

int last=1;

struct interval
	{	
		int x,y;
	}; 
	
interval f[100010];
	
bool cmp(interval a,interval b)
	{
		return a.y<b.y;
	}

int bs(int val,int dr)
{
	int st=1,med,last=0;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if(f[med].y<=val)
			{	
				last=med;
				st=med+1;
			}
		else
			dr=med-1;
	}
	return last;
}	

int c[100001];

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i,poz;
	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);
	c[0]=0;
	c[1]=f[1].y-f[1].x;
	for(i=2;i<=n;i++)
	{
		c[i]=c[i-1];
		poz=bs(f[i].x,i-1);
		if(c[poz]+f[i].y-f[i].x>c[i])
			c[i]=c[poz]+f[i].y-f[i].x;
	}
	printf("%d",c[n]);
	return 0;
}