HashCode 2020 - MorePizza

#include <bits/stdc++.h>
#define ull unsigned long long

using namespace std;

int M, N, value;
vector<long long int> values;
vector<vector<long long int> > dp;
vector<int> path;

long long int getSubSetSum(int idx, int sum) {
    if(idx == N) return 0;
    if(dp[idx][sum] == -1) {
        dp[idx][sum] = getSubSetSum(idx + 1, sum);
        if(sum - values[idx] >= 0) {
            dp[idx][sum] = max(values[idx] + getSubSetSum(idx + 1, sum - values[idx]), dp[idx][sum]);
        }
    }

    return dp[idx][sum];
}

void pathSubSetSum(int idx, long long int sum) {
    if(idx == N) return;
    long long int a = getSubSetSum(idx + 1, sum);
    if(sum - values[idx] >= 0) {
        long long int b = values[idx] + getSubSetSum(idx + 1, sum - values[idx]);
        if(b > a) {
            pathSubSetSum(idx + 1, sum - values[idx]);
            path.push_back(idx);
        } else {
            pathSubSetSum(idx + 1, sum);
        }
    } else {
        pathSubSetSum(idx + 1, sum);
    }
}

long long int MAX_OPERATIONS = 300000001;

int main(void) {
    //freopen ("in.in", "r", stdin);
    //freopen ("e_also_big.out", "w", stdout);
    cin >> M >> N;

    for(int i = 0; i < N; i++) {
        cin >> value;
        values.push_back(value);
    }

    unsigned long long int sum = 0;
    int stopIdx = -1;
    unsigned long long int currentSum = 0;

    for(int i = N - 1; i >= 0; i--) {
        if(((ull) M - (ull) sum) * ((ull) N - (ull)i) <= (ull) MAX_OPERATIONS) {
            stopIdx = i;
            currentSum = (ull) M - (ull) sum;
            break;
        }
        sum += values[i];
        path.push_back(i);
    }

    N = stopIdx + 1;
    dp = vector<vector<long long int> >(stopIdx + 1, vector<long long int>(currentSum + 1, -1));

    pathSubSetSum(0, currentSum);
    sort(path.begin(), path.end());

    cout << path.size() << endl;
    for(int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
    cout << endl;
    return 0;
}