Cod sursa(job #163791)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 23 martie 2008 10:27:52
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<stdio.h>
#include<string.h>
FILE*fin=fopen("peste.in","r");
FILE*fout=fopen("peste.out","w");
#define maxn 50001
int n,k,rez[maxn],tt,p[maxn],timp[maxn],te[1001],smax[1001];
void rec(int nod,int dim)
{
  int nd=nod,min=p[nod],st,dr;
  st=nod<<1;dr=st+1;
  if(st<=dim&&p[st]<min){nd=st;min=p[st];}
  if(dr<=dim&&p[dr]<min){nd=dr;min=p[dr];}
  if(nd!=nod)
  {
    p[nd]^=p[nod]^=p[nd]^=p[nod];
    timp[nd]^=timp[nod]^=timp[nd]^=timp[nod];
    rec(nd,dim);
  }
}
void ord()
{
  int i;
  for(i=n/2;i>=1;i--)
    rec(i,n);
  int dim=n;
  while(dim>1)
  {
    p[dim]^=p[1]^=p[dim]^=p[1];
    timp[dim]^=timp[1]^=timp[dim]^=timp[1];
    dim--;
    rec(1,dim);
  }
}
int main()
{
  int i,tmax=0,t,l;
  memset(te,0,sizeof(te));
  fscanf(fin,"%d%d%d",&n,&k,&tt);
  for(i=1;i<=n;i++)
  {
    fscanf(fin,"%d%d",&p[i],&timp[i]);
    if(timp[i]>tmax) tmax=timp[i];
    te[timp[i]]=1;
  }
  fclose(fin);
  ord();
  for(t=1;t<=tmax;t++)
    if(te[t])
    {
      l=0;
      for(i=1;i<=n&&l<k;i++)
	if(timp[i]<=t)
	{
	  smax[t]+=p[i];
	  l++;
	}
    }
  rez[0]=0;
  for(t=1;t<=tt;t++)
  {
    rez[t]=rez[t-1];
    for(i=1;i<=t&&i<=tmax;i++)
      if(te[i]) if(rez[t-i]+smax[i]>rez[t]) rez[t]=rez[t-i]+smax[i];
  }
  fprintf(fout,"%d",rez[tt]);
  fclose(fout);
  return 0;
}