Pagini recente » Monitorul de evaluare | Monitorul de evaluare | cartele2 | Statistici David Dragostin (DavvDrg) | Cod sursa (job #491330)
Cod sursa(job #491330)
#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,mheap;
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);
t++;
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
vmax=maxim(vmax,v[i].y+1);
}
sort(v+1,v+n+1,cmp);
poz=1;
for(i=1;i<=t;i++)
{
prod[i]=prod[i-1];
while(poz<=n && v[poz].y+1==i)
{
heap.push(v[poz].x);
poz++;
}
if(heap.empty())
continue;
fol++;
val=heap.top();
prod[i]+=val;
heap.pop();
///////
mheap.push(-val);
if(fol==k+1)
{
prod[i]+=mheap.top();
fol--;
mheap.pop();
}
}
for(i=1;i<=t;i++)
for(j=maxim(i-vmax-1,0);j<i;j++)
d[i]=maxim(d[i],d[j]+prod[i-j]);
printf("%lld\n",d[t]);
return 0;
}