제출 #194110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
194110		rama_pang	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	573 ms	347564 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;

int N, L;
int A[105];
lint memo[105][105][1005][2][2];

lint dp(int n, int comp, int cost, int l, int r) {
    // l = left border
    // r = right border
    int new_cost = cost + (n > 0 ? A[n] - A[n - 1] : 0) * (2 * comp + l + r);
    if (new_cost > L) {
        return 0;
    }
    if (comp < 0) {
        return 0;
    }
    if (n == N - 1) {
        return comp == 0 ? 1 : 0;
    }

    lint &res = memo[n][comp][cost][l][r];
    if (res != -1) {
        return res;
    }

    res = 0;

    res += dp(n + 1, comp, new_cost, 1, r); // connect A[n] to left border
    res += dp(n + 1, comp - 1, new_cost, 1, r) * comp; // merge a component and left border
    
    res += dp(n + 1, comp, new_cost, l, 1); // connect A[n] to right border
    res += dp(n + 1, comp - 1, new_cost, l, 1) * comp; // merge a component and right border
    
    res += dp(n + 1, comp + 1, new_cost, l, r); // new component
    res += dp(n + 1, comp, new_cost, l, r) * comp * 2; // connect to middle component
    res += dp(n + 1, comp - 1, new_cost, l, r) * comp * (comp - 1); // merge two middle component

    res %= MOD;
    return res;
}

int main() {
    memset(memo, -1, sizeof(memo));

    cin >> N >> L;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    sort(A, A + N);

    cout << dp(0, 0, 0, 0, 0) << "\n";
    return 0;
}

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