Cod sursa(job #2536109)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 1 februarie 2020 15:17:28
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 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;
	if(pza<pzb)
		return true;
	if(pza>pzb)
		return false;
	return a.fel>b.fel;
}
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;
}