Cod sursa(job #2642444)

Utilizator anabatAna Batrineanu anabat Data 15 august 2020 13:06:31
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define NMAX 100000

struct elem{
  int st;
  int dr;
  int lung;
};

struct elem v[NMAX+1];

bool comp(elem a,elem b){
  if(a.dr<b.dr){
    return true;
  }
  else if(a.dr==b.dr&&a.st<b.st){
    return true;
  }
  return false;
}

int d[NMAX+1];

int cbin(int i){
  int st,dr,mij;
  st=0;
  dr=i-1;
  while(st<dr){
    mij=(st+dr)/2;
    if(v[mij].dr<=v[i].st){
      st=mij+1;
    }
    else{
      dr=mij-1;
    }
  }
}

int main()
{
  FILE *fin,*fout;
  fin=fopen("heavymetal.in","r");
  fout=fopen("heavymetal.out","w");

  int n,i,poz;
  fscanf(fin,"%d",&n);
  for(i=0;i<n;i++){
    fscanf(fin,"%d%d",&v[i].st,&v[i].dr);
    v[i].lung=v[i].dr-v[i].st;
  }
  std::sort(v,v+n,comp);
  for(i=0;i<n;i++){
    poz=cbin(i);
    d[i]=std::max(d[poz]+v[i].lung,d[i-1]);
  }
  fprintf(fout,"%d",d[n-1]);

  fclose(fin);
  fclose(fout);
  return 0;
}