Cod sursa(job #2040803)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 16 octombrie 2017 16:06:43
Problema Peste Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <algorithm>
#include <queue>
#define DIM 50002

using namespace std;

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

int n, k, T, d[DIM], s, aux[DIM];

class compare
{
public:
    bool operator() (int a, int b)
    {
        return a > b;
    }
};

priority_queue <int, vector<int>, compare> h;

struct plasa
{
    int p, t;
}v[DIM];

bool cmp(plasa a, plasa b)
{
    if(a.t == b.t)
        return a.p < b.p;
    return a.t < b.t;
}

int main()
{
    f>>n>>k>>T;
    for(int i = 1; i <= n; ++ i)
        f>>v[i].p>>v[i].t;
    sort(v + 1, v + n + 1, cmp);
    for(int i = 1; i <= v[i].t; ++ i)
    {
        h.push(v[i].p);
        s += v[i].p;
        if(h.size() > k)
        {
            s -= h.top();
            h.pop();
        }
        aux[v[i].t] = max(aux[v[i].t], s);
    }
    for(int i = 1; i <= T; ++ i)
        for(int j = 0; j <= min(i, v[n].t); ++ j)
            d[i] = max(d[i], d[i - j] + aux[j]);
    g<<d[T];

    return 0;
}