Cod sursa(job #1224284)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 30 august 2014 13:37:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

#define NMAX 100001

struct trupa {
	int x,y;
	bool operator < (const trupa &c) const {
		if(y==c.y)
			return x<c.x;
		return y<c.y;
	}
};

trupa v[NMAX];
int t[NMAX];

int cbin(int p, int q, int x)
{
	int sol,mij;
	sol=0;
	while(p<=q) {
		mij=(p+q)/2;
		if(v[mij].y<=x) {
			sol=mij;
			p=mij+1;
		}
		else q=mij-1;
	}
	return sol;
}

int main ()
{
	int n,i,poz;
	ifstream f("heavymetal.in");
	ofstream g("heavymetal.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i].x>>v[i].y;
	f.close();
	sort(v+1,v+n+1);
	t[1]=v[1].y-v[1].x;
	for(i=2;i<=n;i++) {
		poz=cbin(1,i-1,v[i].x);
		t[i]=max(t[poz]+v[i].y-v[i].x,t[i-1]);
	}
	g<<t[n];
	g.close();
	return 0;
}