Unable to figure out my mistake in 1316E.

Revision en15, by JDC, 2024-08-18 22:15:37

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) &mdash; 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;
}
Tags dynamic programming, bitmask, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English JDC 2024-08-18 22:15:37 0 (published)
en14 English JDC 2024-08-18 21:34:48 170
en13 English JDC 2024-08-18 21:34:06 0 Tiny change: ':\n6 2 3\n78 93 9 ' -> ':\n6 2 3\n\n78 93 9 '
en12 English JDC 2024-08-18 21:33:30 0 Tiny change: ' 17\n56 68\n60 36\n84 ' -> ' 17\n56 6860 36\n84 '
en11 English JDC 2024-08-18 21:33:10 13
en10 English JDC 2024-08-18 21:32:46 210
en9 English JDC 2024-08-18 21:31:27 291
en8 English JDC 2024-08-18 21:28:52 12
en7 English JDC 2024-08-18 21:28:15 7
en6 English JDC 2024-08-18 21:27:23 6
en5 English JDC 2024-08-18 21:27:03 244 Reverted to en1
en4 English JDC 2024-08-18 21:26:07 244
en3 English JDC 2024-08-18 21:25:31 312 Reverted to en1
en2 English JDC 2024-08-18 21:25:20 312 (saved to drafts)
en1 English JDC 2024-08-18 20:53:26 1952 Initial revision (published)