Cod sursa(job #595353)

Utilizator maritimCristian Lambru maritim Data 12 iunie 2011 02:09:18
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define MaxN 100100

typedef struct
{
	int x;
	int y;
} xy;

xy A[MaxN];
int B[MaxN];
int N;
int MAX;
int a;
int b;

bool cmp(xy a,xy b)
{
	if(a.x == b.x)
		return a.y > b.y;
	return a.x < b.x;
}

int max(int a,int b)
{
	return a>b ? a:b;
}

int main()
{
	FILE *f = fopen("heavymetal.in","r");
	FILE *g = fopen("heavymetal.out","w");
	
	fscanf(f,"%d ",&N);
	for(int i=1;i<=N;i++)
		fscanf(f,"%d %d ",&A[i].x,&A[i].y);
	sort(A+1,A+N+1,cmp);
	B[1] = A[1].y - A[1].x;
	for(int i=1;i<=N;i++)
	{
		int j; int k;
		for(j = i + 1;j<=N && A[i].y>A[j].x;j++);
		for(k = j;k<=N && A[j].y>A[k].x;k++)
			B[k] = max(B[i] + A[k].y - A[k].x,B[k]);
		if(MAX < B[i])
			MAX = B[i];
	}
	fprintf(g,"%d ",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}