Cod sursa(job #2059128)

Utilizator shantih1Alex S Hill shantih1 Data 6 noiembrie 2017 17:58:39
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int n, i, j, s, rez, mx, dp[100005];
int st, dr, mid, a, b;

struct metal
{	int in, sf, d;	} v[100005];

bool comp(metal a, metal b)
{
	if (a.in == b.in)	return a.sf < b.sf;
	return a.in < b.in;
}

int main () {
	
	fin>>n;	
	for (i = 1; i <= n; i++)
	{
		fin >> v[i].in >> v[i].sf;
		v[i].d = v[i].sf-v[i].in;
	}
	
	//sort (v+1, v+n+1, comp);
	
	dp[1] = v[1].sf-v[1].in;
	for (i = 2; i <= n; i++)
	{
		a = v[i].in;	b = v[i].sf;
		mx = 0;
		for (j = 1; j < i; j++)
		{
			if (dp[j] > mx && (v[j].sf <= a || v[j].in >= b))		
				mx = dp[j];
		}
		dp[i] = mx+b-a;
		if (dp[i] > rez)	rez = dp[i];
	}
	
	fout << rez << "\n";
}