Submission #1294287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294287		Zakir060	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	40 ms	23848 KiB

skyscraper

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

using ll = long long;
const ll MOD = 1000000007;

// dp[i][j][k][z]:
// i – yerləşdirilən bina sayı (ən kiçik i dənə)
// j – bağlı komponentlərin sayı
// k – ümumi məsrəf (boş yerlər a[i] kimi sayılır)
// z – neçə uc (baş/sontam) doldurulub: 0,1,2
ll dp[101][101][1001][3];
ll a[101];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, L;
    if (!(cin >> n >> L)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a, a + n);

    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    a[n] = 10000;

    int diff0 = a[1] - a[0];

    if (diff0 <= L)
        dp[1][1][diff0][1] = 2;  // 2 uc var

    if (2 * diff0 <= L)
        dp[1][1][2 * diff0][0] = 1;
 for (int i = 1; i < n; ++i) {
        int diff = a[i + 1] - a[i];  // boş yerlərin dəyərinin artımı

        for (int j = 1; j <= i; ++j) {
                for (int k = 0; k <= L; ++k) {
                for (int z = 0; z < 3; ++z) {
                    ll cur = dp[i][j][k][z];
                    if (!cur) continue;

                    if (z < 2) {
                        ll base = k + 1LL * diff * (2 * j - z - 1);
                        if (base <= L) {
                            if (i == n - 1) {
                                dp[i + 1][j][base][z + 1] =
                                    (dp[i + 1][j][base][z + 1] +
                                     cur * (2 - z) * j) % MOD;
                            } else if (z == 0 || j > 1) {
                                dp[i + 1][j][base][z + 1] =
                                    (dp[i + 1][j][base][z + 1] +
                                     cur * (2 - z) * (j - z)) % MOD;
                            }
                        }

                        base = k + 1LL * diff * (2 * j - z + 1);
                        if (base <= L) {
                            dp[i + 1][j + 1][base][z + 1] =
                                (dp[i + 1][j + 1][base][z + 1] +
                                 cur * (2 - z)) % MOD;
                        }
                    }


                    ll base2 = k + 1LL * diff * (2 * j - z + 2);
                    if (base2 <= L) {
                        dp[i + 1][j + 1][base2][z] =
                            (dp[i + 1][j + 1][base2][z] + cur) % MOD;
                    }

                    base2 = k + 1LL * diff * (2 * j - z);
                    if (base2 <= L) {
                        dp[i + 1][j][base2][z] =
                            (dp[i + 1][j][base2][z] +
                             cur * (2 * j - z)) % MOD;
                    }

                    base2 = k + 1LL * diff * (2 * j - z - 2);
                    if (base2 <= L && j >= 2 &&
                        (i == n - 1 || j > 2 || z < 2)) {
                        if (z == 0) {
                            dp[i + 1][j - 1][base2][z] =
                                (dp[i + 1][j - 1][base2][z] +
                                 cur * j * (j - 1)) % MOD;
                        } else if (z == 1) {
                            dp[i + 1][j - 1][base2][z] =
                                (dp[i + 1][j - 1][base2][z] +
                                 cur * (j - 1) * (j - 1)) % MOD;
                        } else {
                            if (i == n - 1) {
                                dp[i + 1][j - 1][base2][z] =
                                    (dp[i + 1][j - 1][base2][z] + cur) % MOD;
                            } else {
                                dp[i + 1][j - 1][base2][z] =
                                    (dp[i + 1][j - 1][base2][z] +
                                     cur * (j - 2) * (j - 1)) % MOD;
                            }
                        }
                    }
                }
            }
        }
    }

    ll ans = 0;
    for (int cost = 0; cost <= L; ++cost) {
        ans = (ans + dp[n][1][cost][2]) % MOD;
    }

    cout << ans << '\n';
    return 0;
}

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