My solution which gives MLE on tc 11
int n, W;
cin >> n >> W;
vi w(n + 1), v(n + 1);
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
vvi dp(n + 1, vi(W + 1, 0));
for (int i = n; i >= 1; i--) {
for (int weight = 0; weight <= W; weight++) {
int exclude = 0;
if (i + i <= n) exclude = dp[i + i][weight];
int include = 0;
if (w[i] <= weight) {
include = v[i];
for (int jump = i; i + jump <= n; jump += i) {
if (weight >= w[i]) {
include = max(include, v[i] + dp[i + jump][weight - w[i]]);
}
}
}
dp[i][weight] = max(include, exclude);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i][W]);
}
cout << ans << "\n";
How to solve it? ;)
image added if the link is not accesible(wrong spelling nvm)
It says I am not allowed to view the contest.
I think what you need to do is reduce the size of your
dp
array. To calculate values ofdp[i]
you only usedp[i-1]
. You can throwaway the older values. This is called the "alternating row trick" sometimes because to calculate one row of thedp
matrix you only need the previous one.but since the problem requires us to jump only in such forms i ... i+i .... i+2*i so i don't think that is possible
Is the contest ongoing? If so, you are not allowed to ask for help. If not, please share proof that it isn't from an ongoing contest.
no,it is over, it was yesterday, if you aren't sure then you can maybe help me few hours later :)
Auto comment: topic has been updated by thequacker (previous revision, new revision, compare).
Deleted
Come to 301 when you will be free, I will explain why there is MLE.
okay sir :)
sir isme state rotation lagega kya? like knapsack 2 of atcoder?