Pagini recente » Cod sursa (job #2335364) | Cod sursa (job #2957178) | Cod sursa (job #3146539) | Cod sursa (job #2339164) | Cod sursa (job #1853613)
#include<bits/stdc++.h>
#define maxN 50005
using namespace std;
multiset<int> Set;
pair<int,int> v[maxN];
int x[1005],n,k,ttotal,nr,sum,dp[50005],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]=0;
for(int i=1;i<=v[n].first;i++)
{
x[i]=x[i-1];
while(ind<n && v[ind+1].first<=i)
{
ind++;
Set.insert(v[ind].second);
nr++;
sum+=v[ind].second;
}
while(nr>k)
{
sum-=*Set.begin();
nr--;
Set.erase(Set.begin());
}
x[i]=max(x[i],sum);
}
dp[0]=0;
maxim=0;
for(int i=1;i<=ttotal;i++)
{
dp[i]=maxim;
for(int j=0;j<i;j++)
{
dp[i]=max(dp[i],dp[j]+x[i-j+1]);
}
maxim=max(maxim,dp[i]);
}
printf("%d\n",dp[ttotal]);
return 0;
}