Cod sursa(job #1675295)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 5 aprilie 2016 11:20:12
Problema Peste Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,k,t;
long long bst[50005],peste[1005],s;
pair<int,int>p[50005];
priority_queue<int>q;
int main(void)
{
    int i,j,min1;
    freopen("peste.in", "r", stdin);
    freopen("peste.out", "w", stdout);
    scanf("%d %d %d",&n,&k,&t);
    for(i=1;i<=n;++i)
      scanf("%d %d",&p[i].second,&p[i].first);
    sort(p+1,p+n+1);
    for(i=1;i<=n;++i)
    {
        if(q.size()<k)
        {
            s+=p[i].second;
            q.push(-p[i].second);
        }
        else
        {
            min1=-q.top();
            if(min1<p[i].second)
            {
                s=s-min1+p[i].second;
                q.pop();
                q.push(-p[i].second);
            }
        }
        peste[p[i].first]=s;
    }
    for(i=1;i<=1000;++i)
      if(!peste[i])
        peste[i]=peste[i-1];
    for(i=1;i<=t;++i)
      for(j=1;j<=1000&&j<=i;++j)
        bst[i]=max(bst[i],bst[i-j]+peste[j]);
    printf("%lld\n",bst[t]);
    return 0;
}