[Problem Link(might not work)](https://mirror.codeforces.com/gym/542643/problem/E)↵
↵
↵
↵
[Problem Statement URL](https://drive.google.com/file/d/1ThkvbrktTX9IGVE96LbTatlMnxC9OMGP/view?usp=sharing)↵
↵
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)↵
↵
↵
[Problem Statement URL](https://drive.google.com/file/d/1ThkvbrktTX9IGVE96LbTatlMnxC9OMGP/view?usp=sharing)↵
↵
↵
↵
[Problem Statement URL](https://drive.google.com/file/d/1ThkvbrktTX9IGVE96LbTatlMnxC9OMGP/view?usp=sharing)↵
↵
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)↵
↵
↵
[Problem Statement URL](https://drive.google.com/file/d/1ThkvbrktTX9IGVE96LbTatlMnxC9OMGP/view?usp=sharing)↵
