Cod sursa(job #595397)

Utilizator maritimCristian Lambru maritim Data 12 iunie 2011 12:24:47
Problema Heavy metal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#include<algorithm>
#include<assert.h>
using namespace std;

#define MaxN 100100
#define mij (li + ls) / 2
#define ll long long

typedef struct
{
	int x;
	int y;
} xy;

xy A[MaxN];
ll B[MaxN];
int N;
ll MAX;
ll a;
ll b;

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

int max(int a,int b)
{
	return a>b ? a:b;
}

ll binary_search(int li,int ls,int a)
{
	if(li <= ls)
	{
		if(A[mij].y == a)
			return B[mij];
		else if(A[mij].y > a)
			return binary_search(li , mij - 1 , a);
		else
			return binary_search(mij + 1 , ls , a);
	}
	else
		return B[ls];
}

int main()
{
	FILE *f = fopen("heavymetal.in","r");
	FILE *g = fopen("heavymetal.out","w");
	
	fscanf(f,"%d ",&N);
	for(int i=1;i<=N;i++)
		fscanf(f,"%llu %llu ",&A[i].x,&A[i].y);
	sort(A+1,A+N+1,cmp);
	B[1] = A[1].y - A[1].x;
	for(int i=2;i<=N;i++)
	{
		B[i] = A[i].y - A[i].x + binary_search(1,i-1,A[i].x);
		if(MAX < B[i])
			MAX = B[i];
		B[i] = MAX;
	}
	assert(MAX>=0);
	fprintf(g,"%llu ",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}