Cod sursa(job #2636336)

Utilizator eusebiu_alexandruMorar Eusebiu eusebiu_alexandru Data 17 iulie 2020 15:49:31
Problema Peste Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 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;
	
}