Cod sursa(job #277857)

Utilizator drag0s93Mandu Dragos drag0s93 Data 11 martie 2009 22:37:16
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

#define IN "heavymetal.in","r",stdin
#define OUT "heavymetal.out","w",stdout

struct pct{
	int min,max;
	int ore;
};

struct pct1{
	int min,max;
};


int n;
pct v[100000];
pct1 stiva[100000];


void citire()
{
	freopen(IN);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&v[i].min,&v[i].max);
		v[i].ore=v[i].max-v[i].min;
	}
}


int cmp(struct pct a,struct pct b)  
{  
	return a.ore>b.ore;  
}  

void solve()
{
	int e=1;
	bool ok=true;
	long long formatii=0;
	for(int i=1;i<=n;++i)
	{
		ok=true;
		for(int p=1;p<=e && ok!=false;++p)
			if((v[i].min>=stiva[p].min && v[i].max<=stiva[p].max) || (v[i].min>=stiva[p].min && v[i].min<=stiva[p].max))
				ok=false;
		if(ok==true)
		{
			stiva[e].min=v[i].min;
			stiva[e].max=v[i].max;
			formatii+=v[i].ore;
		}
	}
	freopen(OUT);
	printf("%d\n",formatii);
}

int main()
{
	citire();
	sort(v+1,v+n+1,cmp);
	solve();
	return 0;
}