Cod sursa(job #2498000)

Utilizator _Tudor_Tudor C _Tudor_ Data 23 noiembrie 2019 13:21:00
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 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 cautBin(int st, int dr, int inceput)
{
	int mij;
	while (st < dr)
	{
		mij = (st + dr) / 2;

		if(form[mij].end < inceput)
			st = mij + 1;
		else
			dr = mij - 1;
	}
	if(form[st].end > inceput)
		return st - 1;
	return st;
}

int main()
{
	read();
	
	for (int i = 1; i <= n; i++)
	{
		int durata  = form[i].end - form[i].start;
		dp[i] = max(dp[i - 1], dp[cautBin(0, i, form[i].start)] + durata);
	}
	fout << dp[n];
}