I went through the editorial and understood the solution using tabulation, but I’m struggling to find the mistake in my memoization approach.
The code fails on testcase-2 & gives output 332 instead of 377.
#include <bits/stdc++.h>
using namespace std;
int n, p, k;
vector<int> ind(n);
vector<ll> 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<int>>& dp, vector<ll> aud, vector<vector<ll>>& game, vector<int>& 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<ll>> game(n, vector<ll>(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<int>> dp(n, vector<int>(1 << p, -1));
cout << helper(k, 0, 0, dp, aud, game, ind) << endl;
return 0;
}