Submission #1345359

#TimeUsernameProblemLanguageResultExecution timeMemory
1345359hoangtien69Skyscraper (JOI16_skyscraper)C++20
100 / 100
242 ms11672 KiB
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 105;

int n, L;
int a[MAXN];

void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> L;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if (n == 1)
    {
        cout << 1 << "\n";
        return 0;
    }
    sort(a + 1, a + n + 1);
    vector<vector<vector<int>>> dp(n + 2, vector<vector<int>>(L + 1, vector<int>(3, 0)));
    dp[1][0][0] = 1;
    dp[1][0][1] = 2;
    for (int i = 2; i <= n; i++)
    {
        vector<vector<vector<int>>> next_dp(n + 2, vector<vector<int>>(L + 1, vector<int>(3, 0)));
        int diff = a[i] - a[i - 1];
        for (int j = 1; j <= i; j++)
        {
            for (int k = 0; k <= L; k++)
            {
                for (int e = 0; e <= 2; e++)
                {
                    if (dp[j][k][e] == 0) continue;
                    int val = dp[j][k][e];
                    int nk = k + diff * (2 * j - e);
                    if (nk > L) continue;
                    add(next_dp[j + 1][nk][e], 1LL * val * (j + 1 - e) % MOD);
                    add(next_dp[j][nk][e], 1LL * val * (2 * j - e) % MOD);
                    if (j >= 2)
                    {
                        add(next_dp[j - 1][nk][e], 1LL * val * (j - 1) % MOD);
                    }
                    if (e < 2)
                    {
                        add(next_dp[j + 1][nk][e + 1], 1LL * val * (2 - e) % MOD);
                    }
                    if (e < 2)
                    {
                        add(next_dp[j][nk][e + 1], 1LL * val * (2 - e) % MOD);
                    }
                }
            }
        }
        dp = next_dp;
    }
    int ans = 0;
    for (int k = 0; k <= L; k++)
    {
        add(ans, dp[1][k][2]);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...