Cod sursa(job #389122)

Utilizator loginLogin Iustin Anca login Data 31 ianuarie 2010 23:08:49
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
# include <fstream>
# include <algorithm>
using namespace std;
struct nod {
	int i, j;};
int n, l[100003], lmax;
nod f[100003]; 

void read ()
{
	ifstream fin ("heavymetal.in");
	fin>>n;
	int x, y;
	for (int i=1;i<=n;i++)
	{
		fin>>x>>y;
		f[i].i=x;
		f[i].j=y;
	}
}

bool fcmp (nod i, nod j)
{
	if (i.i<j.i)return 1;
	if (i.i==j.i && i.j<=j.j) return 1;
	return 0;
}

void dnmc ()
{
	for (int i=1;i<=n;i++)
		l[i]=f[i].j-f[i].i;
	for (int i=1;i<=n;i++)
		for (int j=i-1;j;j--)
			if (f[j].j<=f[i].i && l[j]+(f[i].j-f[i].i)>l[i])
			{
				l[i]=l[j]+(f[i].j-f[i].i);
				if (l[i]>lmax)
					lmax=l[i];
			}
}

int main ()
{
	read ();
	sort (f+1, f+n+1, fcmp);
	dnmc ();
	ofstream fout ("heavymetal.out");
	fout<<lmax;
	return 0;
}