Cod sursa(job #1689453)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 14 aprilie 2016 11:40:57
Problema Peste Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int NM=50005;
const int Size=10*NM;

int Tmax,i,j, T,n,k, profit[NM],poz;
struct pestisor{int p,t;};
pestisor a[NM];
long long d[NM];
char Buffer[Size+4];

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;
    }
}

bool cifra(char c)
{
    return (c>='0' && c<='9');
}

int GetInt()
{
    while(!cifra(Buffer[poz])) ++poz;

    int nr=0;
    while(cifra(Buffer[poz]))
    {
        nr=nr*10+Buffer[poz]-'0';
        ++poz;
    }
    return nr;
}

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

    fread(Buffer, 1, Size, stdin);
    poz=0;

    n=GetInt();k=GetInt();Tmax=GetInt();

    for(i=1; i<=n; ++i)
    {
        a[i].p=GetInt();
        a[i].t=GetInt();
    }
    initialize();

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

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

    return 0;
}