Cod sursa(job #2761605)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 2 iulie 2021 21:00:52
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100003;

int n;

struct elem{
	int x,y;
}v[NMAX];
int dp[NMAX];

bool cmp(elem a,elem b){
	if(a.y == b.y)
		return a.x < b.x;
	return a.y < b.y;
}

int cb(int val,int dr){
	int st = 1,last = 1;
	while(dr-st>=0){
		int mid = (st + dr)>>1;
		if(v[mid].y <= val ){
			st = mid + 1;
			last = mid;
		}else{
			dr = mid - 1;
		}
		
	}
	return last;
}

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&v[i].x,&v[i].y);
	}
	sort(v+1,v+n+1,cmp);
	for(int i=1;i<=n;i++){
		dp[i] = max(dp[i-1], dp[cb(v[i].x,i-1)] + (v[i].y - v[i].x) );
	}
	printf("%d\n",dp[n] );


    return 0;
}