Cod sursa(job #2180764)

Utilizator marius.onescuMarius marius.onescu Data 21 martie 2018 09:37:32
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<bits/stdc++.h>
using namespace std;
const int N=100020;
struct pod{
	int x, y, c;
}a[N];
int p[N],q[N],l=1, dp[N], mx;
void caut(int i){
	int st=1, dr=l, x=a[i].x, m=(st+dr)/2;
	while(st<dr){
		if(q[m]<x)st=m+1; else dr=m;
		m=(st+dr)/2;
	}
	if(q[m]<=x)m++;
	if(m==l+1)l++;
	if(dp[m-1]+a[i].c>dp[m])dp[m]=dp[m-1]+a[i].c;
	p[i]=m;
	q[m]=a[i].y;
	if(dp[m]>mx)mx=dp[m];
}
int cmp(pod b, pod c){
	if(b.y==c.y)return b.x<c.x;
	return (b.y<c.y);
}
int main(){
	ifstream f("heavymetal.in");
	ofstream g("heavymetal.out");
	int n;
	f>>n;
	for(int i=1;i<=n;i++){
		f>>a[i].x>>a[i].y;
		a[i].c=a[i].y-a[i].x;
	}
	sort(a+1,a+1+n, cmp);
	mx=dp[1]=a[1].c;
	p[1]=1;
	q[1]=a[1].x;
	for(int i=2;i<=n;i++){
		caut(i);
	}
	g<<mx;
}