Cod sursa(job #1412972)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 1 aprilie 2015 17:57:22
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>
#include<cstring>

using namespace std;

int n,k,timp,p[50002],t[50002],fol[1002],i,j,ram;
long long ans[50002],peste[50002];

int main()
{
    freopen("peste.in","r",stdin);
    freopen("peste.out","w",stdout);
    scanf("%d%d%d",&n,&k,&timp);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&p[i],&t[i]);
    }
    for(i=1;i<=1000;i++)
    {
        memset(fol,0,sizeof(fol));
        peste[i]=0LL;
        for(j=1;j<=n;j++)
        {
            if(t[j]<=i)
            {
                fol[p[j]]++;
            }
        }
        ram=k;
        for(j=1000;j>=1&&ram;j--)
        {
            if(fol[j])
            {
                if(fol[j]<=ram)
                {
                    peste[i]+=1LL*j*fol[j];
                    ram-=fol[j];
                }
                else
                {
                    peste[i]+=1LL*j*ram;
                    ram=0;
                }
            }
        }
    }
    for(i=0;i<=timp;i++)
    {
        ans[i]=0;
        for(k=1;k<=i;k++)
        {
            if(ans[i-k]+peste[k]>ans[i])
            {
                ans[i]=ans[i-k]+peste[k];
            }
        }
    }
    printf("%lld\n",ans[timp]);
}