Cod sursa(job #2045489)

Utilizator LauraNaduLaura Nadu LauraNadu Data 22 octombrie 2017 14:11:19
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
struct plasa
{
    int pesti;
    int timp;
} a[50003];
bool cmp(plasa a, plasa b)
{
    if(a.timp==b.timp)
        return a.pesti<b.pesti;
    return a.timp<b.timp;
}
class comparare
{
public:
    bool operator()(int a, int b)
    {
        return a>b;
    }
};
priority_queue<int, vector<int>, comparare> heap;
int n, k, total, nrp, v[50003], i, j, best[50003];
int main()
{
    f>>n>>k>>total;
    for(i=1;i<=n;i++)
        f>>a[i].pesti>>a[i].timp;
    sort(a+1,a+n+1, cmp);
    for(i=1;i<=n;i++)
    {
        heap.push(a[i].pesti);
        nrp+=a[i].pesti;
        if(heap.size()>k)
        {
            nrp-=heap.top();
            heap.pop();
        }
        if(v[a[i].timp]<nrp)
            v[a[i].timp]=nrp;
    }
    int minim;
    for(i=1;i<=total;i++)
    {
        if(a[n].timp<i)
            minim=a[n].timp;
        else minim=i;
        for(j=0;j<=i;j++)
            if(best[i]<best[i-j]+v[j])
                best[i]=best[i-j]+v[j];
    }
    g<<best[total];
}