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 this test case: 6 2 3 78 93 9 17 13 78 80 97 30 52 26 17 56 68 60 36 84 55
The expected output is 377, but my solution returns 332. Here’s 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<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;
}