Pagini recente » Cod sursa (job #2816314) | Cod sursa (job #1737683) | Cod sursa (job #852439) | Cod sursa (job #792803) | Cod sursa (job #1206840)
#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;
}