Cod sursa(job #2097317)

Utilizator mihnea00Duican Mihnea mihnea00 Data 30 decembrie 2017 21:57:29
Problema Peste Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

ifstream fin("peste.in");
ofstream fout("peste.out");

priority_queue< int , vector<int> , greater<int> > qu;
int n,m,k,timp,sum,best[50010],aux[50010],j,i,sol;

struct date_plase
{
    int pes,tim;
} v[50010];

bool cmpp(date_plase x, date_plase y)
{
    if(x.tim == y.tim)
        return x.pes < y.pes;
    else
        return x.tim < y.tim;
}

int main()
{
    fin>>n>>k>>timp;

    for(i=1;i<=n;++i)
    {
        fin>>v[i].pes>>v[i].tim;
    }
    sort(v+1,v+n+1,cmpp);

    for(i=1;i<=n;++i)
    {
        qu.push(v[i].pes);
        sol+=v[i].pes;
        if(qu.size() > k)
        {
            sol-=qu.top();
            qu.pop();
        }

        aux[v[i].tim]=max(aux[v[i].tim], sol );

    }

    for(i=1;i<=timp;++i)
    {
        for(j=0; j<=min( i, v[n].tim);++j)
            best[i]=max(best[i],best[i-j]+aux[j]);
    }
    fout<<best[timp];
    return 0;
}