Cod sursa(job #2611381)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 6 mai 2020 19:44:38
Problema Peste Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");

int n,k,T,tmax,maxim;
int dp[1005],cate[1005],rasp[50005];
struct plasa
{
    int p,t;
};
plasa v[50005];
bool cmp(plasa a ,plasa b)
{
    return a.p<b.p;
}
int main()
{
    fin>>n>>k>>T;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].p>>v[i].t;
        tmax=max(tmax,v[i].t);
    }
    sort(v+1,v+n+1,cmp);
    for(int i=n;i>=1;i--)
    {
        if(cate[v[i].t]<k)
        {
            dp[v[i].t]+=v[i].p;
            cate[v[i].t]++;
            for(int j=v[i].t+1;j<=tmax;j++)
            {
                if(cate[j]>=k)break;
                dp[j]+=dp[j-1];
                cate[j]++;
            }
        }
    }
    for(int i=1;i<=tmax;i++)
    {
        for(int j=1;j<=T-i;j++)
        {
            rasp[j+i]=max(rasp[j+i],rasp[j]+dp[i]);
        }
        rasp[i]=max(rasp[i],dp[i]);
    }
    for(int i=T;i>=1;i--)
    {
        maxim=max(maxim,rasp[i]);
    }
    fout<<maxim;
}