Cod sursa(job #1316155)

Utilizator misinozzz zzz misino Data 13 ianuarie 2015 16:23:54
Problema Peste Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<fstream>
#include<queue>
#include<algorithm>

#define N 50100

using namespace std;

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

int n,k,i,t,s,j;

long long a[1010],d[N];

pair<int,int>v[N];

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

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

    for(i = 1; i <= n; ++i)
        f >> v[i].second >> v[i].first;

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

    for(i = 1; i <= n; ++i)
    {
        h.push(v[i].second);

        s += v[i].second;

        if(i > k)
        {
            s -= h.top();
            h.pop();
        }
        a[v[i].first] = s;
    }

    for(i = 1; i <= 1000; ++i)
        a[i] = max(a[i - 1], a[i]);

    for(i = 1; i <= t; ++i)
    {
        for(j = 1; j <= 1000 && j <= i; ++j)
            d[i] = max(d[i], d[i - j] + a[j]);
    }

    g << d[t] << '\n';
    return 0;
}