Submission #1144462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144462		am_aadvik	Skyscraper (JOI16_skyscraper)	C++20	5 / 100	1250 ms	198728 KiB

skyscraper

#include <iostream>
#include<vector>
#include<cstring>
#include<math.h>
using namespace std;

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

vector<int> a;
int n, l;
vector<vector<vector<int>>> dp;

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() {
    cin >> n >> l;
    dp.assign(l + 1, vector<vector<int>>(n + 1, vector<int>(pow(2, n), -1)));
    a.resize(n);
    for (auto& x : a) cin >> x;
    cout << sol(0, 0, n);
}

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