Cod sursa(job #1316377)

Utilizator misinozzz zzz misino Data 13 ianuarie 2015 19:35:23
Problema Peste Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<fstream>
#include<queue>
#include<algorithm>

#define N 50100
#define D 10000

using namespace std;

ofstream g("peste.out");

int n,k,i,t,s,j,poz = D + 1,a[1010];

long long d[N];

char buf[D];

pair<int,int>v[N];

struct cmp{
    bool operator()(const int &a,const int &b)const{
        return a > b;
    }
};

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

inline int ianr(){
    unsigned int nr=0;

    while((buf[poz] < '0' || buf[poz] > '9') && buf[poz] != '-')
        if(++ poz >= D)
        fread(buf , D , 1 , stdin) , poz = 0;

    int semn = 1;

    if(buf[poz] == '-')
    ++ poz , semn = -1;

    while('0' <= buf[poz] && buf[poz] <= '9')
    {
        nr = nr * 10 + buf[poz] - '0';

        if(++ poz >= D)
            fread(buf , D , 1 , stdin) , poz = 0;
    }
    return nr * semn;
}

int main()
{
    freopen("peste.in","r",stdin);
    n = ianr();
    k = ianr();
    t = ianr();

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

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