Cod sursa(job #2034392)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 7 octombrie 2017 19:11:38
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <algorithm>
#include <set>
#define DIM 50002

using namespace std;

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

int n, k, T, val, d[DIM], s, maxim, kk, maximT;

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

multiset <plasa, compare> h;
multiset <plasa, compare>::iterator it;

int main()
{
    f>>n>>k>>T;

    for(int i = 1; i <= n; ++ i)
    {
        f>>v[i].p>>v[i].t;
        if(v[i].t > maximT)
            maximT = v[i].t;
    }

    sort(v + 1, v + n + 1, cmp);

    int j = 1;

    for(int i = 1; i <= maximT; ++ i)
    {
        for(; j <= n; ++ j)
        {
            if(v[j].t <= i)
                h.insert(v[j]);
            else
                break;
        }
        s = 0;
        maxim = 0;
        if(!h.empty())
            it = h.begin();
        for(int l = 1; l <= k; ++ l)
        {
            if(!h.empty() && it != h.end())
            {
                aux = *it;
                s += aux.p;
                if(aux.t > maxim)
                    maxim = aux.t;
                it++;
            }
        }
        d[i] = s + d[i - maxim];
        for(int l = 1; l <= i / 2; ++ l)
        {
            d[i] = max(d[i], d[l] + d[i - l]);
        }
    }
    for(int i = maximT; i <= T; ++ i)
    {
        for(int j = 1; j <= i / 2; ++ j)
        {
            d[i] = max(d[i], d[j] + d[i - j]);
        }
    }

    maxim = 0;

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

    g<<maxim;

    return 0;
}