Pagini recente » Cod sursa (job #2896692) | Cod sursa (job #2855725) | Cod sursa (job #2853356) | Cod sursa (job #3227372) | Cod sursa (job #1854120)
#include<bits/stdc++.h>
#define maxN 50005
using namespace std;
typedef struct tip
{
int a;
};
bool operator<(const tip& a,const tip& b)
{
return a.a>b.a;
}
priority_queue<tip> q;
pair<int,int> v[maxN];
int x[50005],n,k,ttotal,nr,sum;
long long dp[50005];
int maxim;
int main()
{
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d%d%d",&n,&k,&ttotal);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i].first,&v[i].second);
swap(v[i].second,v[i].first);
}
sort(v+1,v+n+1);
int ind=0;
//x[i]-cea mai mare cantitate de peste care poate sa fie prinsa intr-un interval de lungime i
//nr-numarul de elemente din Set
//sum-suma elementelor din Set
x[0]=-INT_MAX;
for(int i=1;i<=n;i++)
{
q.push({v[i].second});
sum+=v[i].second;
if(q.size()>k)
{
sum-=q.top().a;
q.pop();
}
x[v[i].first]=sum;
}
for(int i=1;i<=v[n].first;i++)
{
x[i]=max(x[i],x[i-1]);
}
dp[0]=0;
int m=v[n].first;
for(int i=1;i<=ttotal;i++)
{
dp[i]=0;
int minim=min(i,m);
for(int j=1;j<=minim;j++)
{
dp[i]=max(dp[i],dp[i-j]+x[j]);
}
}
printf("%lld\n",dp[ttotal]);
return 0;
}