Cod sursa(job #595356)

Utilizator maritimCristian Lambru maritim Data 12 iunie 2011 10:22:27
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 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=2;i<=N;i++)
	{
		int j;
		for(j = i-1;j && A[j].y>A[i].x;j--);
		B[i] = A[i].y - A[i].x + B[j];
		if(MAX < B[i])
			MAX = B[i];
		B[i] = MAX;
	}
	fprintf(g,"%d ",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}