Cod sursa(job #2034344)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 7 octombrie 2017 18:48:27
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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, val, d[DIM], s, maxim, kk;

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

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

class compare
{
public:
    bool operator() (plasa a, plasa b)
    {
        if(a.p == b.p)
            return a.t > b.t;
        return a.p < b.p;
    }
};

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

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

    int j = 1;

    for(int i = 1; i <= T; ++ i)
    {
        for(; j <= n; ++ j)
        {
            if(v[j].t <= i)
                h.push(v[j]);
            else
                break;
        }
        s = 0;
        maxim = 0;
        for(int l = 1; l <= k; ++ l)
        {
            if(!h.empty())
            {
                aux = h.top();
                s += aux.p;
                if(aux.t > maxim)
                    maxim = aux.t;
                h.pop();
                folos[++kk] = aux;
            }
        }
        for(int l = 1; l <= kk; ++ l)
            h.push(folos[l]);
        kk = 0;
        d[i] = s + d[i - maxim];
    }

    maxim = 0;

    for(int i = 1; i <= T; ++ i)
        if(d[i] > maxim)
            maxim = d[i];

    g<<maxim;

    return 0;
}