Heyo! If you tried to solve problem D you have probably ended up trying to optimize this algorithm:

    // input
    int n, k;
    cin >> n >> k;
    vector arr(n, vector<int>(n));
    for (int i = 0; i < n;i++)
        for (int j = i; j < n; j++)
            cin >> arr[i][j];

    vector dp(n+2, vector<int>());
    dp[n] = dp[n+1] = {0};

    for (int i = n-1; i >= 0; i--) {
        vector<int> cur;
        for (int j = i-1; j < n; j++) {
            // prepare to merge by adding a[i][j]
            vector<int> tomerge = dp[j+2];
            if (j >= i) {
                for (int& x : tomerge)
                    x += arr[i][j];
            }

            vector<int> merged;
            merge(cur.begin(), cur.end(),
                  tomerge.begin(), tomerge.end(),
                  back_inserter(merged), greater());
            cur = merged;
        }
        dp[i] = cur;
    }

    // output top k values
    for (int i = 0; i < k && i < dp[0].size(); i++)
        cout << dp[0][i] << ' ';
    cout << '\n';

But of course this won't work! The number of values in dp[i] will grow exponentially. But we only need to output first K values of the final dp[0]. Can we do better?

We only need to store first K values for each dp[i]. So we can rewrite: dp[i] = cur; while (dp[i].size() > k) dp[i].pop_back();

This leaves us with O(n^2 k) solution, this time the bottleneck is the merging part. The OFFICIAL solution is to use priority queue to select first K values after merging, without going through all values. But we are not interested in that!

LAZY merging

If you have heard about Haskell, you might know that it's a lazy language, it only computes things when it absolutely needs them -- e.g. when you print them. Could it be the case that just switching our programming language to Haskell make the solution pass? (Spoiler: yes, kindof)