730F - Ber Patio - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int f[5005][10005], ans[5005], pre[5005][10005], a[5005];

int main() {
    int n, m, i, j, k, s = 0;
    cin >> n >> m;
    memset(f, 60, sizeof(f));
    f[0][0] = 0;

    // Input values for array 'a'
    for (i = 1; i <= n; i++) {
        cin >> a[i];
        for (j = 0; j <= 10000; j++) {
            if (f[i - 1][j] <= s) {
                int tp = m + j - s + f[i - 1][j];
                for (k = 0; k <= tp && 2 * k <= a[i]; k++) {
                    int o = j + (a[i] - k) / 10;
                    if (f[i][o] > f[i - 1][j] + a[i] - k) {
                        f[i][o] = f[i - 1][j] + a[i] - k;
                        pre[i][o] = k;
                    }
                }
            }
        }
        s += a[i];
    }

    // Finding the result
    int res = 0;
    for (i = 0; i <= 10000; i++) {
        if (f[n][i] < f[n][res]) {
            res = i;
        }
    }
    cout << f[n][res] << endl;
    for (i = n; i; i--) {
        ans[i] = pre[i][res];
        res -= (a[i] - ans[i]) / 10;
    }
    for (i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }

    return 0;
}