제출 #1144467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144467		am_aadvik	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	908 ms	198724 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: 15 / 15
• Subtask 3: 0 / 80