Cod sursa(job #1856866)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 25 ianuarie 2017 15:54:30
Problema Peste Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <queue>
#include <algorithm>
#define nmax 50005
using namespace std;
ifstream f("peste.in");
ofstream g("peste.out");
struct plasa{int p;int t;} v[nmax];
priority_queue <int,vector <int>,greater<int> > q;
long long d[nmax];
int n,k,t,s,a[nmax];

int comparing(const plasa &a,const plasa &b)
{
    return a.t<b.t;
}

int main()
{
    int i,j;
    f>>n>>k>>t;
    for (i=1;i<=n;i++)
        f>>v[i].p>>v[i].t;
    sort(v+1,v+n+1,comparing);
    for (i=1;i<=n;i++) {
        q.push(v[i].p);
        s+=v[i].p;
        if (q.size()>k) {
            s-=q.top();
            q.pop();
        }
        a[v[i].t]=max(a[v[i].t],s);
    }
    for (i=1;i<=v[n].t;i++)
        a[i]=max(a[i],a[i-1]);

    for (i=1;i<=t;i++)
        for (j=min(i,v[n].t);j>=0;j--)
            d[i]=max(d[i],d[i-j]+a[j]);
    g<<d[t]<<'\n';

    return 0;
}