Блог пользователя JDC

Автор JDC, история, 4 часа назад, По-английски

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;
}
  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
4 часа назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

i just don't get how every single one of those posts have unformated code. If you want someone to read something at least make it pleasable for the guy. it's like a spit at the face, be more respectful

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think everything is wrong with you

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by JDC (previous revision, new revision, compare).