Cod sursa(job #178986)

Utilizator stefanrStefan Ruseti stefanr Data 15 aprilie 2008 14:03:19
Problema Peste Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream.h>
ifstream fin("peste.in");
ofstream fout("peste.out");

struct plasa
{int p,t,s;
 float e;}v[50001];

int n,k,t,e[50001],p;

void schimba(int tip,int i,int j)
{if(tip==0)
  {int aux;
   aux=e[i];
   e[i]=e[j];
   e[j]=aux;
  }
 else
  {plasa aux;
   aux=v[i];
   v[i]=v[j];
   v[j]=aux;
  }
}

int main()
{fin>>n>>k>>t;
int i,j;
for(i=1;i<=n;i++)
 {fin>>v[i].p>>v[i].t;
  e[i]=i;
 }
for(i=1;i<n;i++)
 for(j=i+1;j<=n;j++)
  {if(v[i].t==v[j].t && v[i].p>v[j].p) schimba(1,i,j);
   if(v[i].t>v[j].t) schimba(1,i,j);
  }
for(i=1;i<=n && v[i].t<=t;i++)
 if(i==n || v[i].t!=v[i+1].t)
  {for(j=i;i-j+1<=k && j>=1;j--) v[i].s+=v[j].p;
   v[i].e=v[i].s/v[i].t;
   for(j=i-1;v[j].t==v[i].t && j>=1;j--)
    {v[j].s=v[i].s;
     v[j].e=v[j].s/v[j].t;
    }
  }
n=i-1;
for(i=1;i<n;i++)
 for(j=i+1;j<=n;j++)
  if(v[e[i]].e<v[e[j]].e) schimba(0,i,j);
while(t!=0)
 {for(i=1;v[e[i]].t>t;i++);
  if(i>n) t=0;
  else
   {p+=v[e[i]].s;
    t-=v[e[i]].t;
   }
 }
fout<<p;
fin.close();
fout.close();
return 0;
}