I went through the editorial &and understood the solution throughusing tabulation, but failI’m struggling to find athe mistake in my memoization solution. ↵
Capproach.↵
↵
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↵
E↵
The expected output is 377, butI gotmy solution returns 332.↵
↵
Here i’s my solution, —any help is appreciated:↵
```c++↵
#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<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< j < p; j++) {↵
if (mask & 1 << j) continue;↵
else play = max(play, game[ind[i]][j]+ + helper(a,i+ i + 1, mask | 1 << j, dp, aud, game, ind));↵
}↵
}↵
↵
if (a > 0) {↵
audi = aud[ind[i]]+ + helper(a-1,i+ - 1, i + 1, mask, dp, aud, game, ind);↵
} else {↵
else audi = helper(a,i+ 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 n >> p >> k;↵
↵
vector<vector<ll> > game(n, vector<ll>(p));↵
ind.resize(n);↵
aud.resize(n);↵
↵
for (int i = 0;i< i < n; i++) ind[i] = i;↵
sort(ind.begin(), ind.end(), func);↵
↵
for (int i = 0;i< i < n; i++) cin >> aud[i];↵
↵
for (int i = 0;i< i < n; i++) {↵
for (int j = 0;j< 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;↵
}↵
```↵
C
↵
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
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<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>
if (mask == (1 << p)
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)
for (ll j = 0;
if (mask & 1 << j) continue;↵
else play = max(play, game[ind[i]][j]
}↵
}↵
↵
if (a > 0) {↵
audi = aud[ind[i]]
} else {↵
}↵
↵
return dp[i][mask] = max(audi, play);↵
}↵
↵
static bool func(int i, int j) {↵
return aud[i] > aud[j];↵
}↵
↵
int main()
fastio();↵
cin >>
↵
vector<vector<ll>
ind.resize(n);↵
aud.resize(n);↵
↵
for (int i = 0;
sort(ind.begin(), ind.end(), func);↵
↵
for (int i = 0;
↵
for (int i = 0;
for (int j = 0;
}↵
↵
vector<vector<int>
cout << helper(k, 0, 0, dp, aud, game, ind) << endl;↵
↵
return 0;↵
}↵
