Cod sursa(job #163548)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 22 martie 2008 14:46:22
Problema Peste Scor 50
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 10-a Marime 0.98 kb
#include <stdio.h>
#include <stdlib.h>

long n,k,T,i,j,v[50005];
long tmax,max,q,l;
long a[1005],p[50005],t[50005],ind[50005];

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

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=n+1;
        while (q<k&&i>1){
              i--;
              if (t[ind[i]]<=j){a[j]+=p[ind[i]];q++;}
        }
    }
    
    for (i=0;i<T;i++){
        l=T-i;
        if (tmax<l)l=tmax;
        for (j=1;j<=l;j++)
            if (v[i]+a[j]>v[i+j])v[i+j]=v[i]+a[j];
    }
    max=0;
    for (i=1;i<=T;i++)
        if (max<v[i])max=v[i];

    printf("%ld\n",max);
    
return 0;
}