제출 #474841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474841		SirCovidThe19th	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	2 ms	1228 KiB

skyscraper

#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;
}

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