Cod sursa(job #554535)

Utilizator tudorsTudor Siminic tudors Data 14 martie 2011 22:05:25
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <algorithm>
#define N 100001
using namespace std;

typedef struct {int st,dr;} INTERVAL;
int n,rez;
INTERVAL A[N];
FILE *f,*g;

bool operator < (const INTERVAL &a, const INTERVAL &b)
{
	if (a.st<b.st)
		return 1;
	else if (a.st==b.st)
		if (a.dr<b.dr)
			return 1;
	return 0;
}

void citire()
{
	int i;
	fscanf(f,"%d",&n);
	for (i=1;i<=n;++i)
		fscanf(f,"%d %d",&A[i].st,&A[i].dr);
}

int maxim(int a, int b)
{
	if (a>=b)
		return a;
	else
		return b;
}

void solve()
{
	int mi,ma,i,sc;
	sort(A+1,A+n+1);
	rez=0;
	mi=A[1].st;
	ma=A[1].dr;
	sc=ma-mi;
	for (i=2;i<=n;++i)
		if (A[i].st>=ma)
		{
			rez+=sc;
			mi=A[i].st;
			ma=A[i].dr;
			sc=ma-mi;
		}
		else if (A[i].dr>=ma)
		{
			if (A[i].dr-A[i].st>sc)
			{
				sc=A[i].dr-A[i].st;
				mi=A[i].st;
				ma=A[i].dr;
			}
		}
	rez+=sc;
	fprintf(g,"%d",rez);
}

int main()
{
	f=fopen("heavymetal.in","r");
	g=fopen("heavymetal.out","w");
	
	citire();
	solve();
	
	fclose(f);
	fclose(g);
	return 0;
}