Untitled

 avatar
unknown
plain_text
a year ago
731 B
6
Indexable
int findAns(int index, int lastIndex,vector<int> A, vector<int> B, int K, int N, int Y,vector<vector<vector<int>>> &dp)
{
    if(index<0|| K == 0)
        return 0;
    if(dp[index][lastIndex][K] != -1)
    return dp[index][lastIndex][K];
    int pick = INT_MIN;

    if(lastIndex == N || abs(A[index]- A[lastIndex])<=Y)
     pick = B[index] + findAns(index-1,index,A,B,K-1,N,Y,dp);
     int notPick = findAns(index-1,lastIndex,A,B,K,N,Y,dp);

     return dp[index][lastIndex][K] =  max(pick,notPick);
        


}
int get_ans(int N, int K, int Y, vector<int> A, vector<int> B)
{
    vector<vector<vector<int>>> dp(N+1,vector<vector<int>>(N+1,vector<int>(K+1,-1))) ;
    return findAns(N-1,N,A,B,K,N,Y,dp);

}
Editor is loading...
Leave a Comment