Submission #1210186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210186		badge881	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	1204 ms	235240 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MOD = 1000000007;

int main()
{
    int N, L;
    scanf("%d %d", &N, &L);
    vector<ll> A(N);
    for (int i = 0; i < N; i++)
        scanf("%lld", &A[i]);

    if (N <= 8)
    {
        sort(A.begin(), A.end());
        ll out = 0;
        do
        {
            int tmp = 0;
            for (int i = 0; i < N - 1; i++)
                tmp += abs(A[i] - A[i + 1]);
            if (tmp <= L)
                out++;
        } while (next_permutation(A.begin(), A.end()));
        printf("%lld\n", out % MOD);
    }
    else if (N <= 14)
    {
        vector<vector<vector<ll>>> dp(1 << N, vector<vector<ll>>(N, vector<ll>(L + 1, 0)));
        for (int i = 0; i < N; i++)
            dp[1 << i][i][0] = 1;
        for (int tot = 0; tot <= L; tot++)
        {
            for (int mask = 0; mask < (1 << N); mask++)
            {
                for (int i = 0; i < N; i++)
                {
                    if ((mask & (1 << i)) == 0)
                        continue;
                    int newmask = (mask ^ (1 << i));
                    for (int j = 0; j < N; j++)
                    {
                        if ((newmask & (1 << j)) == 0)
                            continue;
                        if (abs(A[i] - A[j]) <= tot)
                        {
                            dp[mask][i][tot] += dp[newmask][j][tot - abs(A[i] - A[j])];
                            dp[mask][i][tot] = dp[mask][i][tot] % MOD;
                        }
                    }
                }
            }
        }
        ll out = 0;
        for (int tot = 0; tot <= L; tot++)
            for (int i = 0; i < N; i++)
                out = (out + dp[(1 << N) - 1][i][tot]) % MOD;
        printf("%lld\n", out);
    }
    else
    {
        sort(A.begin(), A.end());
        A.push_back(1001);
        ll dp[N][N][L + 1][3];
        fill(&dp[0][0][0][0], &dp[N - 1][N - 1][L][2] + 1, 0);
        // for (int i = 0; i < N; i++)
        //     for (int j = 0; j < N; j++)
        //         for (int k = 0; k <= L; k++)
        //             for (int e = 0; e <= 2; e++)
        //                 dp[i][j][k][e] = 0;

        if (2 * (A[1] - A[0]) <= L)
            dp[0][1][2 * (A[1] - A[0])][0] = 1;
        if (A[1] - A[0] <= L)
            dp[0][1][A[1] - A[0]][1] = 2;
        if (N == 1)
            dp[0][1][0][2] = 1;
        for (int tot = 0; tot <= L; tot++)

            for (int e = 0; e <= 2; e++)

                for (int i = 1; i < N; i++)

                    for (int j = 1; j <= i + 1; j++)
                    {
                        ll inc = (2 * j - e) * (A[i + 1] - A[i]);
                        if (inc > tot || i + 1 + j + 1 - e > N)
                            continue;
                        dp[i][j][tot][e] += dp[i - 1][j - 1][tot - inc][e];
                        if (e > 0)
                            dp[i][j][tot][e] += (2 - (e - 1)) * dp[i - 1][j - 1][tot - inc][e - 1];

                        dp[i][j][tot][e] += (2 * j - e) * dp[i - 1][j][tot - inc][e];
                        if (e == 1)
                            dp[i][j][tot][e] += (2 * j) * dp[i - 1][j][tot - inc][e - 1];
                        if (e == 2 && j == 1)
                        {
                            if (i == N - 1)
                                dp[i][j][tot][e] += dp[i - 1][j][tot - inc][e - 1];
                        }
                        else if (e == 2 && j > 1)
                            dp[i][j][tot][e] += (j - 1) * dp[i - 1][j][tot - inc][e - 1];

                        if (e == 2 && i == N - 1)
                        {
                            if (j == 1)
                                dp[i][j][tot][e] += dp[i - 1][j + 1][tot - inc][e];
                        }
                        else if (e == 2)
                            dp[i][j][tot][e] += j * (j - 1) * dp[i - 1][j + 1][tot - inc][e]; //(j+1)-1 choices of left, (j+1)-2 choice of right.
                        else if (e == 1)
                            dp[i][j][tot][e] += j * j * dp[i - 1][j + 1][tot - inc][e]; //(j+1)j ordered pairs, exclude the j with the endpoint component on the wrong side
                        else
                            dp[i][j][tot][e] += (j + 1) * j * dp[i - 1][j + 1][tot - inc][e];

                        dp[i][j][tot][e] = dp[i][j][tot][e] % MOD;
                    }

        ll out = 0;
        for (int i = 0; i <= L; i++)
            out = (out + dp[N - 1][1][i][2]) % MOD;
        printf("%lld\n", out);
    }
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d", &N, &L);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%lld", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

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