Cod sursa(job #2055071)

Utilizator shantih1Alex S Hill shantih1 Data 2 noiembrie 2017 20:09:29
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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);
	
	mx = 0;
	dp[1] = v[1].sf-v[1].in;
	for (i = 2; i <= n; i++)
	{
		st = 1;		dr = i-1;
		while (st <= dr)
		{
			mid = st+(dr-st)/2;
			if (v[mid].sf > v[i].in)	dr = mid-1;
			if (v[mid].sf <= v[i].in)	st = mid+1;
		}
		if (v[mid+1].sf <= v[i].in)	mid++;
		if (v[mid].sf > v[i].in)	mid--;
		
		dp[i] = dp[mid]+(v[i].sf-v[i].in);
		if (dp[i] < dp[i-1])	dp[i] = dp[i-1];
		if (dp[i] > mx)	mx = dp[i];
	}	
	fout << mx << "\n";
}