Cod sursa(job #491330)

Utilizator edp100Edp100 edp100 Data 10 octombrie 2010 21:37:06
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#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;
}