Cod sursa(job #2103655)

Utilizator shantih1Alex S Hill shantih1 Data 10 ianuarie 2018 17:06:35
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int n,i,j,dp[100005],mb[100005],rz,mx,x;
int st,dr,mid,cb;
struct interv
{	int a, b;} v[100005];
bool comp(interv A,interv B)
{
	if(A.a==B.a)	return A.b<B.b;
	return A.a<B.a;
}

int main () {
	
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i].a>>v[i].b;
	
	sort(v+1,v+n+1,comp);
	
	dp[1]=v[1].b-v[1].a;
	mb[1]=v[1].b;
	rz=dp[1];
	for(i=2;i<=n;i++)
	{
		mx=0,x=0;
		for(j=1;j<i;j++)
			if(mb[j]<=v[i].a&&dp[j]>mx)
				mx=dp[j],x=mb[j];
		dp[i]=mx+v[i].b-v[i].a;
		mb[i]=max(x,v[i].b);
		if(dp[i]>rz)	rz=dp[i];
	}
	
	fout<<rz<<"\n";
}