Pagini recente » Cod sursa (job #1166895) | Cod sursa (job #1557104) | Cod sursa (job #2499845) | Istoria paginii runda/bulangandit3 | Cod sursa (job #492457)
Cod sursa(job #492457)
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
#define maxim(a,b) (a>b ? a : b)
#define ll long long
int n,k,t,poz,vmax;
int prod[1005];
ll d[50006];
priority_queue <int> heap;
struct per
{
int x,y;
};
per v[50006];
int cmp(const per& a,const per& b)
{
return a.y<b.y;
}
int main ()
{
int i,j,val,fol=0;
freopen("peste.in","r",stdin);
freopen("peste.out","w",stdout);
scanf("%d%d%d",&n,&k,&t);
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
vmax=maxim(vmax,v[i].y);
}
sort(v+1,v+n+1,cmp);
poz=1;
for(i=1;i<=vmax;i++)
{
prod[i]=prod[i-1];
while(poz<=n && v[poz].y==i)
{
if(fol<k)
{
heap.push(-v[poz].x);
prod[i]+=v[poz].x;
poz++;
fol++;
continue;
}
val=-heap.top();
heap.pop();
prod[i]-=val;
val=maxim(val,v[poz].x);
prod[i]+=val;
heap.push(-val);
poz++;
}
}
for(i=1;i<=t;i++)
for(j=maxim(i-vmax,0);j<i;j++)
d[i]=maxim(d[i],d[j]+prod[i-j]);
printf("%lld\n",d[t]);
return 0;
}