Cod sursa(job #770740)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 23 iulie 2012 19:03:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <algorithm>

#define st(x) (V[x].first)
#define dr(x) (V[x].second)

using namespace std;

ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");

const int MAXN = 100010;

pair < int, int > V[MAXN];
int Best[MAXN];

bool comp (pair < int, int > a, pair < int, int > b)
{
	return a.second < b.second;
}

int main ()
{
	int N, i, j, now = 1, end;
	
	in >> N;
	
	for (i = 1; i <= N; ++i)
		in >> st(i) >> dr(i);
	
	sort (V + 1, V + N + 1, comp);
	
	end = dr(N);
	
	for (i = 1; i <= end; ++i){
		Best[i] = Best[i - 1];
		
		for ( ; V[now].second == i; ++now)
			if (Best[i] < Best[ st(now) ] + i - st(now))
				Best[i] = Best[ st(now) ] + i - st(now);
	}
	
	out << Best[end];
	
	return 0;
}