Pagini recente » Cod sursa (job #1878776) | Cod sursa (job #1020469) | Cod sursa (job #1296890) | Cod sursa (job #245627) | Cod sursa (job #163445)
Cod sursa(job #163445)
#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;
}