Submission #487974

#	Time	Username	Problem	Language	Result	Execution time	Memory
487974		Alexandruabcde	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	416 ms	99240 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 105;
constexpr int LMAX = 1005;
constexpr int MOD = 1e9 + 7;

int N, L;
int a[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> L;

    for (int i = 1; i <= N; ++ i )
        cin >> a[i];

    sort(a+1, a+N+1);
}

int dp[NMAX][NMAX][LMAX][2][2];

void Add (int &x, int y) {
    x = (1LL * x + 1LL * y) % MOD;
}

void Solve () {
    for (int S = 0; S < 2; ++ S )
        for (int F = 0; F < 2; ++ F )
            dp[1][0][0][S][F] = 1;

    for (int i = 1; i < N; ++ i )
        for (int cnt_space = 0; cnt_space <= N; ++ cnt_space)
            for (int curr_sum = 0; curr_sum <= L; ++ curr_sum)
                for (int S = 0; S < 2; ++ S )
                    for (int F = 0; F < 2; ++ F ) {
                        int new_sum = curr_sum + (a[i+1] - a[i]) * (2 * cnt_space + S + F);

                        if (new_sum > L) continue;

                        if (cnt_space > 0)
                            Add(dp[i+1][cnt_space-1][new_sum][S][F], (1LL * dp[i][cnt_space][curr_sum][S][F] * cnt_space) % MOD);

                        if (cnt_space < N)
                            Add(dp[i+1][cnt_space+1][new_sum][S][F], (1LL * dp[i][cnt_space][curr_sum][S][F] * cnt_space) % MOD);

                        Add(dp[i+1][cnt_space][new_sum][S][F], (1LL * dp[i][cnt_space][curr_sum][S][F] * 2 * cnt_space) % MOD);

                        if (S == 1) {
                            for (int aux_S = 0; aux_S < 2; ++ aux_S) {
                                Add(dp[i+1][cnt_space][new_sum][aux_S][F], dp[i][cnt_space][curr_sum][S][F]);

                                if (cnt_space < N)
                                    Add(dp[i+1][cnt_space+1][new_sum][aux_S][F], dp[i][cnt_space][curr_sum][S][F]);
                            }
                        }

                        if (F == 1) {
                            for (int aux_F = 0; aux_F < 2; ++ aux_F) {
                                Add(dp[i+1][cnt_space][new_sum][S][aux_F], dp[i][cnt_space][curr_sum][S][F]);

                                if (cnt_space < N)
                                    Add(dp[i+1][cnt_space+1][new_sum][S][aux_F], dp[i][cnt_space][curr_sum][S][F]);
                            }
                        }
                    }

    int ans = 0;
    for (int s = 0; s <= L; ++ s )
        ans = (1LL * ans + dp[N][0][s][0][0]) % MOD;

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

int main () {
    Read();
    Solve();

    return 0;
}

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