Submission #1183741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183741		totoro	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	363 ms	243904 KiB

skyscraper

#include <algorithm>
#include <iostream>
#include <vector>

const long long MOD = 1e9 + 7;

inline long long add(long long a, long long b) {
    return ((a + b) % MOD + MOD) % MOD;
}

inline long long mul(long long a, long long b) {
    return (((a * b) % MOD) + MOD) % MOD;
}

inline void addto(long long& dest, long long x) {
    dest = add(dest, x);
}

int main() {
    int n, l;
    std::cin >> n >> l;
    std::vector<int> h(n);
    for (int& i : h) std::cin >> i;
    std::sort(h.begin(), h.end());

    if (n == 1) {
        std::cout << "1\n";
        return 0;
    }

    /*
        dp[i][comp][ends][k] is the number of ways to create `comp` components
        using `ends` ends, with total sum of EXACTLY `k` using first `i` shortest
        buildings

        Note that components are ORDERED, this just makes merging way easier

        dp[0][0][0][0] = 1
        dp[0][!0][or !0][or !0] = 0

        When inserting i, we can insert...
            ... As a new component (not an end), this can go into any of prev(`comp`+1-`ends`)
                = cur(`comp`-`ends`) locations
                It will increase the `k` value by (h[i] - h[i-1]) * prev((2*`comp` - `ends`))
            ... As a new component (on an end), this can go into any of prev(2-`ends`) =
                cur(3-`ends`) locations. Note that cur(`ends`) cannot be 0
                It will increase the `k` value by (h[i]-h[i-1]) * prev((2*`comp`-`ends`))
            ... At the edge of an existing component (not on an end), this can be done in
                prev(2*`comp`-`ends`) ways
                It will increase the `k` value by (h[i]-h[i-1]) * prev(2*`comp`-`ends`)
            ... At the edge of an existing component (on an end), this can be done in prev(2-`ends`)
                ways
                It will increase the `k` value by (h[i]-h[i-1]) * prev(2*`comp`-`ends`)
            ... In between two components, to merge them. This can be done in prev(`comp`-1) ways
                It will increase the `k` value by (h[i]-h[i-1]) * prev(2*`comp`-`ends`)

        Note: we will proceed to do this using a forward dp, cus the logic is much simpler that way
    */

    std::vector<std::vector<std::vector<std::vector<long long>>>> dp(n + 1, std::vector<std::vector<std::vector<long long>>>(n + 1, std::vector<std::vector<long long>>(3, std::vector<long long>(l + 1))));
    dp[0][0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        int heightdiff = (i == 0 ? h[0] : h[i] - h[i - 1]);
        for (int comp = 0; comp <= n; ++comp) {
            for (int ends = 0; ends < 3; ++ends) {
                if (2 * comp - ends < 0) break;
                for (int k = 0; k <= l; ++k) {
                    int newk = k + heightdiff * (2 * comp - ends);
                    if (newk > l) continue;
                    long long cur = dp[i][comp][ends][k];
                    if (comp + 1 <= n) {
                        addto(dp[i + 1][comp + 1][ends][newk], mul(comp + 1 - ends, cur));
                    }
                    if (comp + 1 <= n && ends < 2) {
                        addto(dp[i + 1][comp + 1][ends + 1][newk], mul(2 - ends, cur));
                    }
                    addto(dp[i + 1][comp][ends][newk], mul(2 * comp - ends, cur));
                    if (ends < 2) {
                        addto(dp[i + 1][comp][ends + 1][newk], mul(2 - ends, cur));
                    }
                    if (comp > 0) {
                        addto(dp[i + 1][comp - 1][ends][newk], mul(comp - 1, cur));
                    }
                }
            }
        }
    }
    long long ans = 0;
    for (int k = 0; k <= l; ++k) {
        addto(ans, dp[n][1][2][k]);
    }
    std::cout << ans << '\n';
    return 0;
}

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