Cod sursa(job #2034090)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 7 octombrie 2017 14:02:57
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;
ifstream fin("peste.in");
ofstream fout("peste.out");
struct grup{
    int t;
    int p;
};


int cnp(grup a, grup b)
{
    if(a.t==b.t)
        return a.p<b.p;
    else
        return a.t<b.t;
}


long long i, n,ok, j, aux[50002],k,nr, t;
grup v[50002];
priority_queue <int, vector<int>, greater<int> > w;

int main(){
    fin>>n>>k>>t;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].p>>v[i].t;
    }
    sort(v+1, v+n+1, cnp);
    for(i=1;i<=k;i++)
    {
        aux[v[i].t]=v[i].p+aux[v[i-1].t];
        w.push(v[i].p);
    }
    ok=aux[v[k].t];
    for(i=k+1;i<=n;i++)
    {
        ok+=v[i].p;
        w.push(v[i].p);
        ok-=w.top();
        w.pop();
        aux[v[i].t]=max(aux[v[i].t], ok);
    }
    for(i=1;i<=t;i++)
        for(j=1;j<=i&&j<=1000;j++)
            aux[i]=max(aux[i], aux[i-j]+aux[j]);
    fout<<aux[t];
    fin.close();
    fout.close();
    return 0;
}