I went through the editorial & understood the solution through tabulation, but fail to find a mistake in my memoization solution. Code fails on this testcase: 6 2 3 78 93 9 17 13 78 80 97 30 52 26 17 56 68 60 36 84 55 Expected output is 377 but I got 332.
Here is my solution, any help is appreciated: ```c++
include <bits/stdc++.h>
using namespace std;
define ll long long
define endl '\n'
define tc \
ll tc; \ cin >> tc; \ while (tc--)
define pb push_back
define mp make_pair
const ll MOD = 1e9 + 7; int n,p,k; vector ind(n); vector aud(n); void fastio() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
ll helper(ll a,ll i,ll mask,vector<vector > &dp,vector aud,vector<vector > game,vector &ind){ if(mask == (1<<p)-1 && a == 0) return 0; else if(i == n) return INT_MIN; if(dp[i][mask] != -1) return dp[i][mask]; ll play = INT_MIN; ll audi = INT_MIN; if(mask != (1<<p)-1){ for(ll j = 0;j<p;j++){ if(mask & 1 << j) continue; else play = max(play,game[ind[i]][j]+helper(a,i+1,mask | 1<<j,dp,aud,game,ind)); } } if(a > 0){ audi = aud[ind[i]]+helper(a-1,i+1,mask,dp,aud,game,ind); } else audi = helper(a,i+1,mask,dp,aud,game,ind); return dp[i][mask] = max(audi,play); }
static bool func(int i,int j){ return aud[i] > aud[j]; }
int main() { fastio(); cin>>n>>p>>k; vector<vector > game(n,vector(p)); ind.resize(n); aud.resize(n); for(int i = 0;i<n;i++) ind[i] = i; sort(ind.begin(),ind.end(),func); for(int i = 0;i<n;i++) cin>>aud[i]; for(int i = 0;i<n;i++){ for(int j = 0;j<p;j++) cin>>game[i][j]; } vector<vector > dp(n,vector(1<<p,-1)); cout<<helper(k,0,0,dp,aud,game,ind)<<endl; return 0; } ```