Pagini recente » Cod sursa (job #1813831) | Cod sursa (job #131389) | Cod sursa (job #2072786) | Cod sursa (job #1047852) | Cod sursa (job #1780396)
#include <stdio.h>
#include <algorithm>
#define MAXN 1000
struct concert{
int b, e;
} v[MAXN+1];
int pa[MAXN+1], d[MAXN+1], PUTERE=1;
bool comp(int x, int y){
if(v[x].e<v[y].e)
return true;
else if(v[x].e==v[y].e && v[x].b<v[y].b)
return true;
return false;
}
int CB(int x){
int pas=PUTERE, rez=0;
for(pas/=2;pas>0;pas/=2)
if(v[pa[rez+pas]].e<=v[pa[x]].b)
rez+=pas;
return rez;
}
int main()
{
int n, i, max;
FILE *fi=fopen("heavymetal.in", "r"), *fo=fopen("heavymetal.out", "w");
fscanf(fi, "%d", &n);
while(PUTERE<n)
PUTERE*=2;
for(i=1;i<=n;i++){
fscanf(fi, "%d%d", &v[i].b, &v[i].e);
pa[i]=i;
}
std::sort(pa+1,pa+n+1,comp);
max=0;
for(i=1;i<=n;i++){
d[pa[i]]=d[pa[CB(i)]]+v[pa[i]].e-v[pa[i]].b;
if(d[pa[i]]>max)
max=d[pa[i]];
}
fprintf(fo, "%d", max);
fclose(fi);
fclose(fo);
return 0;
}