Cod sursa(job #1853651)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 21 ianuarie 2017 22:10:57
Problema Peste Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<bits/stdc++.h>
#define maxN 50005
using namespace std;
multiset<int> Set;
pair<int,int> v[maxN];
int x[1005],n,k,ttotal,nr,sum,dp[50005],maxim;
int main()
{
    freopen("peste.in","r",stdin);
    freopen("peste.out","w",stdout);
    scanf("%d%d%d",&n,&k,&ttotal);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].first,&v[i].second);
        swap(v[i].second,v[i].first);
    }
    sort(v+1,v+n+1);
    int ind=0;
    //x[i]-cea mai mare cantitate de peste care poate sa fie prinsa intr-un interval de lungime i
    //nr-numarul de elemente din Set
    //sum-suma elementelor din Set
    x[0]=0;
    for(int i=1;i<=v[n].first;i++)
    {
        x[i]=x[i-1];
        while(ind<n && v[ind+1].first<=i)
        {
            ind++;
            Set.insert(v[ind].second);
            nr++;
            sum+=v[ind].second;
        }
        while(nr>k)
        {
            sum-=*Set.begin();
            nr--;
            Set.erase(Set.begin());
        }
        x[i]=max(x[i],sum+x[i-v[ind].first]);
    }
    dp[0]=0;
    maxim=0;
    for(int i=1;i<=ttotal;i++)
    {
        dp[i]=maxim;
        for(int j=0;j<i;j++)
        {
            dp[i]=max(dp[i],dp[j]+x[i-j+1]);
        }
        maxim=max(maxim,dp[i]);
    }
    printf("%d\n",dp[ttotal]);
    return 0;
}