Cod sursa(job #173916)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 8 aprilie 2008 11:58:01
Problema Peste Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>

long n,k,T,i,j;
long tmax,q,l;
long a[1024],p[50024],t[50024],ind[50024];
long long max,v[50024],aux;

int comp(const void * n1, const void *n2){
    return (p[*((long*)n2)]-p[*((long*)n1)]);
}

int main(){
    freopen("peste.in","r",stdin);
    freopen("peste.out","w",stdout);

    scanf("%ld %ld %ld",&n,&k,&T);

    tmax=0;
    for (i=1;i<=n;++i){
        scanf("%ld %ld",&p[i],&t[i]);
         if (t[i]>tmax)tmax=t[i];
        ind[i]=i;
    }

    qsort(ind+1,n,sizeof(long),comp);

    for (j=1;j<=tmax;++j){
        a[j]=0;
        q=0;i=0;
         while(q<k&&i<n){
              ++i;
              if (t[ind[i]]<=j){a[j]+=p[ind[i]];++q;}
        }
    }
    
    for (i=0;i<T;++i){
        l=(T-i<tmax)?T-i:tmax;

        for (j=1;j<=l;++j){
            aux=(long long)v[i]+a[j];
            if (aux>v[i+j])v[i+j]=aux;
        }
    }

    max=0;
    for (i=1;i<=T;++i)
        if (max<v[i])max=v[i];
    printf("%lld\n",max);

return 0;
}