제출 #474841

#제출 시각아이디문제언어결과실행 시간메모리
474841SirCovidThe19thSkyscraper (JOI16_skyscraper)C++17
15 / 100
2 ms1228 KiB
#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)

int N, L, A[105]; long long dp[105][105][1005][3], ans, md = 1e9 + 7;

int main(){
    cin >> N >> L; dp[0][0][0][0] = 1;
    FOR(i, 1, N + 1) cin >> A[i];
    sort(A + 1, A + N + 1);
    FOR(i, 1, N + 1) FOR(j, 1, N + 1) FOR(l, 1, L + 1) FOR(m, 0, 3){
        long long dif = abs(A[i] - A[i + 1]) * (2 * j - m), &DP = dp[i][j][l][m];
        if (l - dif < 0) continue;
        DP += dp[i - 1][j + 1][l - dif][m] * j; //merge
        DP += dp[i - 1][j][l - dif][m] * (2 * j - m); //append
        DP += dp[i - 1][j - 1][l - dif][m] * (j - m); //new

        if (m) DP += dp[i - 1][j][l - dif][m - 1] * m; //append
        if (m) DP += dp[i - 1][j - 1][l - dif][m - 1] * m; //new

        DP %= md;
        if (i == N and j == 1 and m == 2) ans = (ans + DP) % md;
    }
    cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...