Cod sursa(job #1206840)

Utilizator victormarinMarin Victor victormarin Data 11 iulie 2014 12:33:49
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxim(a,b) (a>b)?a:b
#define filein "heavymetal.in"
#define fileout "heavymetal.out"
using namespace std;

struct BAND
{
	int x;
	int y;
};

BAND v[100001];
int d[100001];

int n;
int TIME;

bool Cmp(BAND a,BAND b);
int FindBand(int start,int finish,int key);

void ReadData();
void BuildArray();
void FindBestMix();
void PrintData();

int main()
{
    ReadData();
    sort(v+1,v+n+1,Cmp);
	BuildArray();
	FindBestMix();
    PrintData();
    return 0;
}

void ReadData()
{
	FILE *in;
	in=fopen(filein,"r");
	fscanf(in,"%d",&n);
	int i;
	for (i=1; i<=n; i++)
		fscanf(in,"%d%d",&v[i].x,&v[i].y);
	fclose(in);
}

void BuildArray()
{
	int i,j;
	d[1]=v[1].y-v[1].x;
	for (i=2; i<=n; i++)
	{
		j=FindBand(1,i-1,v[i].x);
		d[i]=d[i-1];
		d[i]=maxim(d[i],d[j]+v[i].y-v[i].x);
	}
}

void FindBestMix()
{
	int i;
	for (i=1; i<=n; i++)
		if (TIME<d[i]) TIME =d[i];
}

void PrintData()
{
	FILE *out;
	out=fopen(fileout,"w");
	fprintf(out,"%d",TIME);
	fclose(out);
}

bool Cmp(BAND a,BAND b)
{
	return a.y<b.y;
}

int FindBand(int start,int finish,int key)
{
	int mij,last=0;
	while (start<=finish)
	{
		mij=(start+finish)>>1;
		if (v[mij].y<=key)
		{
			last=mij;
			start=mij+1;
		}
		else finish=mij-1;
	}
	return last;
}