Submission #1217194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217194		arwakhattab	Skyscraper (JOI16_skyscraper)	C++20	In queue	0 ms	0 KiB

skyscraper

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';

const int mod = 1e9 + 7;

inline int add(int a, int b) {
    int ans = a + b;
    if (ans >= mod) ans -= mod;
    return ans;
}

inline int mul(int a, int b) {
    return (1ll * a * b) % mod;
}

const int N = 101;
map<int, int> dp[2][2][N][N];

void solve() {
    int n, diff;
    cin >> n >> diff;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    if (n == 1) {
        cout << 1 << nl;
        return;
    }
    if (n == 2) {
        if (abs(a[1] - a[0]) <= diff) {
            cout << 2 << nl;
        } else {
            cout << 0 << nl;
        }
        return;
    }
    a.push_back(0);
    sort(all(a));
    auto go = [&](auto &&go, int i, int j, int k, int f, int l) -> int {
        if (i == 0) return !(j || k || f || l);
        if (dp[f][l][i][j].contains(k)) return dp[f][l][i][j][k];
        int ret = 0;

        // add new component in the middle if possible
        if (j - f - l > 0 && j) ret = add(ret, mul(go(go, i - 1, j - 1, k + 2 * a[i], f, l), j - f - l));

        if (f) {
            // add new component at the beginning if possible
            if (j) ret = add(ret, go(go, i - 1, j - 1, k + a[i], 0, l));

            // merge to a component at the beginning if possible
            ret = add(ret, go(go, i - 1, j, k - a[i], 0, l));
        }

        if (l) {
            // add new component at the end if possible
            if (j) ret = add(ret, go(go, i - 1, j - 1, k + a[i], f, 0));

            // merge to a component at the end if possible
            ret = add(ret, go(go, i - 1, j, k - a[i], f, 0));
        }

        // merge to the beginning or end of a component if possible
        if (2 * j - f - l > 0) ret = add(ret, mul(go(go, i - 1, j, k, f, l), 2 * j - f - l));

        // merge two components if possible
        if (j + 1 <= n) ret = add(ret, mul(go(go, i - 1, j + 1, k - 2 * a[i], f, l), j));

        dp[f][l][i][j][k] = ret;
        return ret;
    };
    int ans = 0;
    for (int i = 0; i <= diff; i++) {
        ans = add(ans, go(go, n, 1, i, 1, 1));
    }
    cout << ans << nl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef LOCAL
    freopen("../in.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}