Cod sursa(job #2908252)

Utilizator ClaudiuChelceaClaudiuChelcea ClaudiuChelcea Data 2 iunie 2022 13:02:27
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct interval
{int a,b;};
int best[1000000];
interval v[100000];
int compar(const interval &x,const interval &y)
{
	if(x.b<y.b)
		return true;
	if(x.b>y.b)
		return false;
	if(x.a<y.a)
		return true;
	return false;
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int n,i,x,j=0,aux;
	scanf("%d",&n);
	for(i=0; i<n; ++i)
		scanf("%d%d",&v[i].a,&v[i].b);
	sort(v,v+n,compar);
	x=v[n-1].b;
	for(i=1; i<=x; ++i)
	{
		best[i]=best[i-1];
		while(i==v[j].b)
		{
			aux=best[v[j].a]+v[j].b-v[j].a;
			if(aux>best[i])
				best[i]=aux;
			j++;
		}
	}
	printf("%d\n",best[x]);
	return 0;
}