Cod sursa(job #178173)

Utilizator MciprianMMciprianM MciprianM Data 14 aprilie 2008 10:30:21
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
using namespace std;
struct Interval {
      int inc,  sf;
}   a[100001], aux;
int n, s, best[100001];
int part(int st,int dr){
  int i=st, j=dr, ii=0,jj=-1,au;
  while(i<j){
    if(a[i].sf>a[j].sf){
      aux=a[i];
      a[i]=a[j];
      a[j]=aux;
      au=ii;
      ii=-jj;
      jj=-au;
    }
    i+=ii;
    j+=jj;
  }
  return i;
}
void qsort(int st, int dr){
    if(st<dr){
      int m=part(st,dr);
       qsort(st,m-1);
       qsort(m+1,dr);
    }
}
inline int max(int a, int b){
  return a>b?a:b;
}
int main(){
  int i,j;
  ifstream f("heavymetal.in");
  f>>n;
  for(i=1;i<=n;i++)
    f>>a[i].inc>>a[i].sf;
  f.close();
  qsort(1,n);
  for(i=1;i<=n;i++){
    int k,b;
    best[i]=a[i].sf-a[i].inc;
    b=best[i];
    for(k=1;k<i&&k<4001;k++){
      if(a[i-k].sf<=a[i].inc)
       b=max(b,best[i-k]+best[i]);
      else b=max(b,best[i-k]);
    }
    best[i]=b;
  }
  ofstream g("heavymetal.out");
  g<<best[n]<<'\n';
  g.close();
  return 0;
}