Here is my approach for the question 2005C - Lazy Narek

I have made my 2 DP Functions and Memoized both of them

I have used 0/1 Knapsack approach in both DPs (Please Tell Me about the Error in the Logic Guys)

#include <bits/stdc++.h>
using namespace std;
#define int long long

unordered_map<int, char> narek = {{0, 'n'}, {1, 'a'}, {2, 'r'}, {3, 'e'}, {4, 'k'}};

map<pair<int, int>, int> memo_dp1;
map<tuple<int, int, int>, int> memo_dp2;

int dp1(vector<string>& a, int i, int found, int n, int m);
int dp2(string& word, int j, int found, int m, vector<string>& a, int i, int n);
void solve();

int32_t main()
{
  int t;
  cin >> t;
  while (t--)
  {
    memo_dp1.clear();
    memo_dp2.clear();
    solve();
  }
}

void solve()
{
  int n, m;
  cin >> n >> m;
  vector<string> a(n);
  for(string& s: a) cin >> s;
  cout << dp1(a, 0, 0, n, m) << "\n";
}

int dp1(vector<string>& a, int i, int found, int n, int m)
{
  if(i >= n) return -found;
  
  auto key = make_pair(i, found);
  if(memo_dp1.find(key) != memo_dp1.end()) return memo_dp1[key];
  
  int exclude = dp1(a, i + 1, found, n, m);
  int include = dp2(a[i], 0, found % 5, m, a, i, n);
  
  return memo_dp1[key] = max(include, exclude);
}

int dp2(string& word, int j, int found, int m, vector<string>& a, int i, int n)
{
  if(j >= m)
  {
    return dp1(a, i + 1, found, n, m);
  }
  
  auto key = make_tuple(i, j, found);
  if(memo_dp2.find(key) != memo_dp2.end()) return memo_dp2[key];
  
  int include = 0;
  int exclude = dp2(word, j + 1, found, m, a, i, n);
  
  if(word[j] == 'n' || word[j] == 'a' || word[j] == 'r' || word[j] == 'e' || word[j] == 'k')
  {
    if(narek[found % 5] == word[j])
    {
      if((found + 1) % 5 == 0) include = 5; 
      include += dp2(word, j + 1, (found + 1) % 5, m, a, i, n);
    }
    exclude -= 1;
  }
  
  return memo_dp2[key] = max(include, exclude);
}