Submission #1144456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144456		am_aadvik	Skyscraper (JOI16_skyscraper)	C++20	0 / 100	259 ms	589824 KiB

skyscraper

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

#define int long long
const int mod = 1e9 + 7;

vector<int> a;
int n, l, dp[100][100][17000];

int sol(int mask, int cl, int prv) {
    if (cl > l) return 0;
    if (mask == (pow(2, n) - 1)) return 1;
    if (dp[cl][prv][mask] != -1) return dp[cl][prv][mask];

    dp[cl][prv][mask] = 0;
    for (int i = 0; i < n; ++i)
        if (!(mask & (1 << i)))
            dp[cl][prv][mask] = (dp[cl][prv][mask] + sol(mask | (1 << i), cl + ((prv == n) ? 0 : abs(a[prv] - a[i])), i) % mod);
    return dp[cl][prv][mask];
}

int32_t main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> l;
    a.resize(n);
    for (auto& x : a) cin >> x;
    cout << sol(0, 0, n);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80