Cod sursa(job #851085)

Utilizator stoicatheoFlirk Navok stoicatheo Data 9 ianuarie 2013 15:17:16
Problema Peste Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
 
struct nr
{
    int x, y;
} p[50010];
 
int cmp(nr a, nr b)
{
    return a.y<b.y;
}
 
int n, k, t, l, a[1010];
long long r[50010];
multiset <int> s;
 
int main()
{
    freopen("peste.in","r",stdin);
    freopen("peste.out","w",stdout);
    scanf("%d %d %d",&n,&k,&t);
    int i, x, y, c, j;
    for (i=1; i<=n; i++) 
    {
        scanf("%d %d",&p[i].x, &p[i].y);
        l=max(l,p[i].y);
    }
    sort (p+1, p+n+1, cmp);
    j=0;
    x=0;
    for (i=1; i<=l; i++)
    {
        for (; p[j].y<=i && j<=n; j++) 
        {
            s.insert(p[j].x);
            x+=p[j].x;
        }
        for (; s.size()>k; ) 
        {
            x-=*s.begin();
            s.erase(s.begin());
        }
        a[i]=x;
    } 
    for (i=1; i<=t; i++)
        for (j=1; j<=min(i,l); j++)
            r[i]=max(r[i], r[i-j]+a[j]);
    printf("%lld\n",r[t]);
}