Cod sursa(job #2104177)

Utilizator shantih1Alex S Hill shantih1 Data 11 ianuarie 2018 12:32:02
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int n,i,j,dp[100005],mx[100005],rz;
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;
	mx[1]=v[1].a;
	rz=dp[1];
	for(i=2;i<=n;i++)
	{
		st=1;   dr=i-1;
		while(st<=dr)
		{
			mid=st+(dr-st)/2;
			if(mx[mid]>=v[i].b)   st=mid+1;
			if(mx[mid]<v[i].b) 	  dr=mid-1;
		}
		while(mx[mid]<v[i].b&&mid>0)	mid--;
		while(mx[mid+1]>=v[i].b&&mid<i-1)	mid++;
		
		if(dp[mid]+v[i].b-v[i].a>dp[i-1])
		{
			dp[i]=dp[mid]+v[i].b-v[i].a;
			mx[i]=v[i].a;
		}
		else
		{
			dp[i]=dp[i-1];
			mx[i]=mx[i-1];
		}
	}
	fout<<dp[n]<<"\n";
}