Cod sursa(job #1413371)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 1 aprilie 2015 20:39:59
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

#define NMAX 50007
#define p second
#define t first

ifstream f("peste.in");
ofstream g("peste.out");

int Tt,N,K,i,j,tmax;
long long sum;
pair < int , int > x[NMAX];
long long d[NMAX],bst[NMAX];
priority_queue < int > pq;

void readprec()
{
    f >> N >> K >> Tt;
    Tt += 1;

    for (i=1;i<=N;++i)
    {
        f >> x[i].p >> x[i].t;
        tmax = max (tmax , x[i].t);
    }

    sort(x+1,x+N+1);
}

void buildd()
{
    j = 1;

    for (i=1;i<=tmax;++i)
    {
        // in i unitati de timp, vad cati pesti prind

        while (j<=N && x[j].t <= i)
        {
            pq.push(-x[j].p);
            sum += 1ll * x[j].p;
            ++j;
        }

        while (pq.size() > K)
        {
            sum += 1ll * pq.top();
            pq.pop();
        }

        d[i+1] = sum;
    }
    tmax += 1;

    /*
    for (i=1;i<=tmax;++i)
    g << d[i] << '\n';

    g << "////////////////////////" << '\n';
    */
}

void solve()
{
    for (i=1;i<=Tt;++i)
    for (j=1;j<=min(i,tmax);++j)
    bst[i] = max(bst[i] , bst[i-j+1] + d[j]);

    g << bst[Tt] << '\n';
}

int main()
{

readprec();
buildd();
solve();

return 0;
}