Cod sursa(job #1862699)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 30 ianuarie 2017 10:28:21
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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;
  return 0;
}

int best[131073];

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

int main()
{
    FILE *fin, *fout;
    int n,a,b,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;
    for(i=1;i<=max;i++){
      best[i]=best[i-1];
      while(v[j].dr<=i){
        best[i]=maxim(best[i],best[v[j].st]+(v[j].dr-v[j].st));
        j++;
      }
    }
    fprintf(fout,"%d",best[max]);
    fclose(fin);
    fclose(fout);
    return 0;
}