Pagini recente » Cod sursa (job #2700739) | Cod sursa (job #2906984) | Cod sursa (job #2104882) | Cod sursa (job #164729) | Cod sursa (job #485505)
Cod sursa(job #485505)
#include <queue>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define FORi(i,s,d) for(i=(s);i<(d);++i, H[i] = H[i-1])
#define nmax 50005
#define tmax 1005
typedef long long lint;
priority_queue <short> Q;
pair <int,int> P[nmax];
int n,k,T,H[tmax];
lint A[nmax],sol;
int main()
{
int i,j;
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d %d %d",&n,&k,&T);
FOR(i,0,n)
{
scanf("%d %d",&P[i].y,&P[i].x);
}
sort(P,P+n);
for ( int i = 0, j = 1, l = 0; j <= 1000; ++j, H[j] = H[j - 1] )
{
for(;i<n && P[i].x==j;Q.push(-P[i].y),l++,H[j]+=P[i++].y);
for(;k<l;H[j]+=Q.top(),Q.pop(),--l);
}
FOR(i,0,T+1)
{
if(A[i]>sol) sol=A[i];
FOR(j,1,1001)
if(A[i+j]<A[i]+H[j])
A[i+j]=A[i]+H[j];
}
printf("%lld",sol);
return 0;
}