Submission #660469

#	Time	Username	Problem	Language	Result	Execution time	Memory
660469		four_specks	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	321 ms	11468 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

const long MOD = 1'000'000'007;

void solve()
{
    int n;
    int l;
    cin >> n >> l;

    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    sort(a.begin(), a.end());

    vector dp(3, vector(l + 1, vector<long>(3, 0)));
    dp[0][0][0] = 1;
    for (int i = 0; i < n - 1; i++)
    {
        vector nxt_dp(i + 4, vector(l + 1, vector<long>(3, 0)));
        for (int j = 1; j <= i + 1; j++)
        {
            for (int x = 0; x <= l; x++)
            {
                for (int k = 0; k <= 2; k++)
                {
                    long cost = (2 * j - k) * (a[i + 1] - a[i]);
                    if (x >= cost)
                    {
                        // create new component w/o endpoint
                        nxt_dp[j][x][k] += (j - k) * dp[j - 1][x - cost][k];

                        // create new component w/ endpoint
                        if (k >= 1)
                            nxt_dp[j][x][k] += (3 - k) * dp[j - 1][x - cost][k - 1];

                        // add to component w/o endpoint
                        nxt_dp[j][x][k] += (2 * j - k) * dp[j][x - cost][k];

                        // add to component w/ endpoint
                        if (k >= 1)
                            nxt_dp[j][x][k] += (3 - k) * dp[j][x - cost][k - 1];

                        // merge two components
                        nxt_dp[j][x][k] += j * dp[j + 1][x - cost][k];

                        nxt_dp[j][x][k] %= MOD;
                    }
                }
            }
        }

        dp = move(nxt_dp);
    }

    long cnt = 0;
    if (n == 1)
        cnt = 1;
    else
    {
        for (int x = 0; x <= l; x++)
            cnt += dp[1][x][1] + dp[2][x][2];
        cnt %= MOD;
    }

    cout << cnt << '\n';
}

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

    solve();

    return 0;
}

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