Cod sursa(job #2497968)

Utilizator _Tudor_Tudor C _Tudor_ Data 23 noiembrie 2019 12:55:59
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
#pragma warning(disable : 4996)

using namespace std;

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

const int NMax = 100000;

int dp[NMax + 5];
int n;

struct Formatie
{
	int start, end;
} form[NMax + 5];

bool operator < (Formatie a, Formatie b)
{
	if(a.end != b.end)
		return a.end < b.end;
	else
		return a.start < b.start;
}

void read()
{
	fin >> n;
	for(int i = 1; i <= n; i++)
		fin >> form[i].start >> form[i].end;

	sort(form + 1, form + n + 1);
}

int main()
{
	read();

	

	for (int i = 1; i <= n; i++)
	{
		int inceput = form[i].start;
		int durata  = form[i].end - form[i].start;
		int j;

		for(j = i - 1; j > 0; j--)
			if(form[j].end <= inceput)
				break;

		dp[i] = max(dp[i - 1], dp[j] + durata);
	}
	fout << dp[n];
}