Submission #47506592

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 23;

ll f[1 << N], s[N][N][N], a[N], b[N];

int n; ll c;

ll dp(int mask) {
    if (f[mask] != -1) {
        return f[mask];
    }
    int cnt = __builtin_popcount(mask);
    int x = 1;
    ll res = 1e18;
    // cout << bs << endl;
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 0; j+i <= n; ++j) {
            if ((mask & (x << j)) == (x << j)) {
                res = min(res, dp(mask ^ (x << j)) + s[i][cnt-i][j] + c);
            }
        }
        x = x * 2 + 1;
    }
    // cout << bs << ' ' << res << endl;
    return f[mask] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> c;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    for (int d = 1; d <= n; ++d) {
        for (int i = 0; i+d <= n; ++i) {
            for (int j = 0; j+d <= n; ++j) {
                for (int k = 0; k < d; ++k) {
                    s[d][i][j] += abs(a[i+k] - b[j+k]);
                }
            }
        }
    }
    for (int i = 0; i < (1 << n); ++i) {
        f[i] = -1;
    }
    f[0] = 0;
    cout << dp((1 << n) - 1) - c << endl;
}

Submission Info

Judge Result