Knapsack restoring answer

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define mp make_pair

using namespace std;

const int maxn = 1e2 + 5;
const int maxs = 1e5 + 5;

int n, m[maxn], c[maxn], M;
int dp[105][10005], p[105][10005];
bool used[10005];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> n >> M;
    for (int i = 1; i <= n; ++i)
        cin >> m[i];
    for (int i = 1; i <= n; ++i)
        cin >> c[i];

    used[0] = true;
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i)
        for (int sum = M; sum >= 0; --sum) {
            dp[i][sum] = dp[i - 1][sum];
            p[i][sum] = p[i - 1][sum];

            int x = sum - m[i];

            if (x >= 0 && dp[i][sum] < dp[i - 1][x] + c[i]) {
                dp[i][sum] = dp[i - 1][x] + c[i];
                p[i][sum] = i;
            }
        }

    int mx = 0, s = -1;

    for (int sum = M; sum >= 0; --sum)
        if (dp[n][sum] > mx) {
            mx = dp[n][sum];
            s = sum;
        }

    int sum = s;

    vector < int > ans;

    for (int i = n; i >= 1; --i) {
        int j = p[i][sum];
        if (i == j) {
            ans.pb(i);
            sum -= m[i];
        }
    }

    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i] << endl;

    return 0;
}