Cod sursa(job #1862874)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 30 ianuarie 2017 13:14:03
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

struct concert{
  int st;
  int dr;
};

concert v[100000];

int cmp(concert a, concert b){
  if(a.dr<b.dr)
    return 1;
  else	if(a.dr==b.dr && a.st<=b.st)
	return 1;
  return 0;
}

int best[100000];

int maxim(int a, int b){
  if(a<b)
    a=b;
  return a;
}

int main()
{
    FILE *fin, *fout;
    int n,i,j,max;
    fin=fopen("heavymetal.in","r");
    fout=fopen("heavymetal.out","w");
    fscanf(fin,"%d",&n);
    max=0;
    for(i=0;i<n;i++){
      fscanf(fin,"%d%d",&v[i].st,&v[i].dr);
      if(max<v[i].dr)
        max=v[i].dr;
    }
    sort(v,v+n,cmp);
    j=0;
    best[0]=v[0].dr-v[0].st;
    for(i=1;i<n;i++){
      best[i]=best[i-1];
      int rez=0;
      for(int pas=1<<17;pas;pas>>=1){
      	if(rez+pas<i && v[rez+pas].dr<=v[i].st)
			rez+=pas;
      }
	  best[i]=maxim(best[i],best[rez]+(v[i].dr-v[i].st));
    }
    fprintf(fout,"%d",best[n-1]);
    fclose(fin);
    fclose(fout);
    return 0;
}