Cod sursa(job #195699)

Utilizator ConsstantinTabacu Raul Consstantin Data 20 iunie 2008 22:10:13
Problema Heavy metal Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<fstream.h>
struct sir{int a,b,t;};
sir a[100000];
int n,max,i,j,k,l,m;
int divide(int p,int q)
	{int st=p,dr=q;
	sir x=a[st];
	while(st<dr&&x.a<=a[dr].a)dr--;
	a[st]=a[dr];
	while(st<dr&&x.a>=a[st].a)st++;
	a[dr]=a[st];
	a[st]=x;
	return st;}
void sortare(int p,int q)
	{if(p<q)
	{int k=divide(p,q);
	sortare(p,k-1);
	sortare(k+1,p);
	}}
int main()
{ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f>>n;
for(i=1;i<=n;i++)
	{f>>a[i].a>>a[i].b;
	a[i].t=a[i].b-a[i].a;
	}
sortare(1,n);
max=0;
for(i=2;i<=n;i++)
	{max=0;
	for(j=1;j<=i-1;j++)
	if(a[j].b<=a[i].a&&a[j].t>max)
		max=a[j].t;
	a[i].t+=max;
	if(a[i].t>m)
	m=a[i].t;
	}
g<<m;
f.close();
g.close();
return 0;
}