Cod sursa(job #2536107)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 1 februarie 2020 15:14:47
Problema Heavy metal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream cin ("heavymetal.in");
ofstream cout ("heavymetal.out");
struct ura
{
	int st,dr;
	short fel;
	int pz;
}v[200005];
bool cmp (ura a, ura b)
{
	int pza;
	if(a.fel==1)
		pza=a.st;
	else
		pza=a.dr;
	int pzb;
	if(b.fel==1)
		pzb=b.st;
	else
		pzb=b.dr;
	return pza<pzb;
}
int dp[100005][2];
int main()
{
	int mxc=0,n,m,i,j=0;
	cin>>n;
	for(i=1;i<=n;++i)
	{
		int a,b;
		cin>>a>>b;
		v[++j]={a,b,1,i};
		v[++j]={a,b,2,i};
	}
	sort(v+1,v+2*n+1,cmp);
	for(i=1;i<=2*n;++i)
	{
		if(v[i].fel==1)
			dp[v[i].pz][0]=mxc;
		else
			dp[v[i].pz][1]=max(mxc,dp[v[i].pz][0]+v[i].dr-v[i].st);
		mxc=max(mxc,dp[v[i].pz][1]);
	}
	cout<<mxc;
    return 0;
}