Cod sursa(job #1076808)

Utilizator andreiiiiPopa Andrei andreiiii Data 10 ianuarie 2014 16:46:33
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <algorithm>
#include <cstdio>
#include <queue>
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N=50005;

PII a[N];
int b[N], c[N];

int main()
{
    freopen("pesti.in", "r", stdin);
    freopen("pesti.out", "w", stdout);
    int t, n, k, i, j, s=0;
    priority_queue <int, vector<int>, greater<int>> h;
    scanf("%d%d%d", &n, &k, &t);
    for(i=1;i<=n;i++) scanf("%d%d", &a[i].y, &a[i].x);
    sort(a+1, a+n+1);
    for(i=1;i<=n;i++)
    {
        s+=a[i].y;
        h.push(a[i].y);
        if(i>k)
        {
            s-=h.top();
            h.pop();
        }
        c[a[i].x]=s;
    }
    for(i=1;i<=1000;i++) if(c[i]<c[i-1]) c[i]=c[i-1];
    for(i=1;i<=t;i++)
    {
        for(j=1;i-j>=0&&j<=1000;j++)
        {
            if(b[i]<b[i-j]+c[j]) b[i]=b[i-j]+c[j];
        }
        if(b[i]<b[i-1]) b[i]=b[i-1];
    }
    printf("%d", b[t]);
}