Cod sursa(job #1688691)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 13 aprilie 2016 17:55:41
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int NM=50005;

int Tmax,i,j, T,n,k, profit[NM];
struct pestisor{int p,t;};
pestisor a[NM];
long long d[NM];

priority_queue< int, vector<int>, greater<int> > Heap;

bool cmp(pestisor a, pestisor b)
{
    return (a.t<b.t);
}

void initialize()
{
    sort(a+1, a+n+1, cmp);
    int i, ind=1, Sum=0;
    T=a[n].t;

    for(i=1; i<=T; ++i)
    {
        while(a[ind].t==i)
        {
            if(Heap.size()<k)
            {
                Sum += a[ind].p;
                Heap.push(a[ind].p);
            }
            else
            if(Heap.size()==k && Heap.top()<=a[ind].p)
            {
                    Sum += a[ind].p-Heap.top();
                    Heap.pop();
                    Heap.push(a[ind].p);
            }
            ++ind;
        }
        profit[i]=Sum;
    }
}

int main()
{
    freopen("peste.in", "r", stdin);
    freopen("peste.out", "w", stdout);

    scanf("%d%d%d", &n, &k, &Tmax);

    for(i=1; i<=n; ++i)  scanf("%d%d", &a[i].p, &a[i].t);

    initialize();

    for(i=1; i<=Tmax; ++i)
    {
         d[i]=d[i-1];
         for(j=1; i>=j && j<=T; ++j)
            d[i]=max( d[i], d[i-j] + profit[j]);
    }

    printf("%lld\n", d[Tmax]);

    return 0;
}