제출 #1369927

#제출 시각아이디문제언어결과실행 시간메모리
1369927Born_To_LaughSkyscraper (JOI16_skyscraper)C++17
100 / 100
85 ms105720 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 1e9 + 7, INF = 1e9 + 7;
const int maxn = 110;
const int maxl = 1010;
ll dp[maxn][maxn][maxl][4];
int n, l;
int a[maxn];
void solve(){
    cin >> n >> l;
    for(int i=1; i<=n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    dp[1][1][0][0] = dp[1][1][0][2] = 1;
    dp[1][1][0][1] = 2;
    for(int i=1; i<n; ++i){
        for(int j=1; j<=i; ++j){
            for(int e=0; e<=2; ++e){
                ll cost = (ll)(2 * j - e) * (a[i + 1] - a[i]);
                for(ll x=cost; x<=l; ++x){
                    ll lon = dp[i][j][x - cost][e];
                    dp[i + 1][j + 1][x][e] = (dp[i + 1][j + 1][x][e] + lon * (j + 1 - e)) % MOD;
                    dp[i + 1][j + 1][x][e + 1] = (dp[i + 1][j + 1][x][e + 1] + lon * (2 - e)) % MOD;

                    dp[i + 1][j][x][e] = (dp[i + 1][j][x][e] + lon * (2 * j - e)) % MOD;
                    dp[i + 1][j][x][e + 1] = (dp[i + 1][j][x][e + 1] + lon * (2 - e)) % MOD;

                    dp[i + 1][j - 1][x][e] = (dp[i + 1][j - 1][x][e] + lon * (j - 1)) % MOD;
                }
            }
        }
    }
    ll ans = 0;
    for(int x=0; x<=l; ++x){
        ans = (ans + dp[n][1][x][2]) % MOD;
    }
    cout << ans << '\n';
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…