Cod sursa(job #492439)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 14 octombrie 2010 16:42:30
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;

#define maxim(a,b) (a>b ? a : b)

int n,k,t,poz,vmax;
int prod[1005],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);
    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<=vmax;i++)
    {
        prod[i]=prod[i-1];
        while(poz<=n && v[poz].y+1==i)
        {
            if(fol<k)
            {
                heap.push(-v[poz].x);
                prod[i]+=v[poz].x;
                poz++;
                fol++;
                continue;
            }
            val=-heap.top();
            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("%d\n",d[t]);
    return 0;
}