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: #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;** }