Cod sursa(job #2331692)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 29 ianuarie 2019 20:00:54
Problema Peste Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<fstream>
#include<algorithm>
#include<queue>
#define p second
#define t first
using namespace std;
ifstream fi("peste.in");
ofstream fo("peste.out");
int n,k,T,i,j,sumq,Nrpesti[1005];
pair<int,int> A[50005];
priority_queue<int> Q;
long long Dp[50005];
int main()
{
    fi>>n>>k>>T;
    for(i=1; i<=n; i++)
        fi>>A[i].p>>A[i].t;
    sort(A+1,A+n+1);
    for(i=1; i<=n; i++)
    {
        sumq+=A[i].p;
        Q.push(-A[i].p);
        if(Q.size()>k)
        {
            sumq+=Q.top();
            Q.pop();
        }
        Nrpesti[A[i].t]=sumq;
    }
    for(i=1; i<=1000; i++)
        Nrpesti[i]=max(Nrpesti[i],Nrpesti[i-1]);
    for(i=1; i<=T; i++)
    {
        Dp[i]=Dp[i-1];
        for(j=1; j<=min(i,1000); j++)
            Dp[i]=max(Dp[i],Dp[i-j]+Nrpesti[j]);
    }
    fo<<Dp[T]<<"\n";
    fi.close();
    fo.close();
    return 0;
}