Cod sursa(job #1780396)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 16 octombrie 2016 09:11:26
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#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;
}