Cod sursa(job #178954)

Utilizator K0nTr0LBucatea Madalin Stefan K0nTr0L Data 15 aprilie 2008 13:31:53
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
#define dim [50001]
struct auxiliar{
long long p,nr;
} aux[1001];
long long n,ttotal,k,i,j,l,p dim,m,best dim,t dim,h dim,tmax;
FILE *in,*out;

void heap(int i){
int s,d,max,l;
while(i<<1<=m){
 s=i<<1;d=s+1;max=i;
  if(p[h[max]]<p[h[s]])
   max=s;
  if(d<=m&&p[h[max]]<p[h[d]])
   max=d;
  if(max-i){
   l=h[i];h[i]=h[max];h[max]=l;i=max;
  }
  else
   return;
}
}

int main(){
//citire
in=fopen("peste.in","rt");
out=fopen("peste.out","wt");
fscanf(in,"%lld%lld%lld",&n,&k,&ttotal);
for(i=1;i<=n;i++){
 fscanf(in,"%lld%lld",&p[i],&t[i]),h[i]=i;
  if(tmax<t[i])
   tmax=t[i];
}
//end
//calculez aux
m=n;
aux[tmax+1].nr=k;
for(i=n/2;i;i--)
 heap(i);
for(;m;m--){
  for(i=t[h[1]];aux[i].nr-k;i++)
   aux[i].p+=p[h[1]],aux[i].nr++;
 h[1]=h[m];
 heap(1);
}
//end
for(i=1,l=0;i-ttotal-1;i++,l=0){
  for(j=1;j-tmax-1&&j-i-1;j++)
    if(l<aux[j].p+best[i-j])
     l=aux[j].p+best[i-j];
 best[i]=l;
}
fprintf(out,"%lld\n",best[ttotal]);
return 0;
}