Submission #250699

#	Time	Username	Problem	Language	Result	Execution time	Memory
250699		parsa_mobed	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	129 ms	47480 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
const int N = 101, L = 1001, MOD = 1e9 + 7;
int a[N], dif[N], dp[N][N][L][3];

int mul(int a, int b) {return 1ll * a * b % MOD;}
void add(int &a, const int &b) {a += b; if (a >= MOD) a -= MOD; return ;}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, s; cin >> n >> s;
    if (n == 1) return cout << 1 << "\n", 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 1; i < n; i++) dif[i] = a[i] - a[i - 1];
    dp[0][0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int k = 0; k <= s; k++) {
                int x = 2 * j, y = j * (j + 1);
                if (k >= x * dif[i]) {
                    add(dp[i][j][k][0], mul(dp[i - 1][j][k - x * dif[i]][0], x));
                    add(dp[i][j][k][0], mul(dp[i - 1][j + 1][k - x * dif[i]][0], y));
                    add(dp[i][j][k][0], dp[i - 1][j - 1][k - x * dif[i]][0]);
                }
                x--, y -= j;
                if (k >= x * dif[i]) {
                    add(dp[i][j][k][1], mul(dp[i - 1][j][k - x * dif[i]][1], x));
                    add(dp[i][j][k][1], mul(dp[i - 1][j + 1][k - x * dif[i]][1], y));
                    add(dp[i][j][k][1], dp[i - 1][j - 1][k - x * dif[i]][1]);
                    add(dp[i][j][k][1], mul(dp[i - 1][j][k - x * dif[i]][0], 2 * j));
                    add(dp[i][j][k][1], mul(dp[i - 1][j - 1][k - x * dif[i]][0], 2));
                }
                x--, y -= j;
                if (k >= x * dif[i]) {
                    add(dp[i][j][k][2], mul(dp[i - 1][j][k - x * dif[i]][2], x));
                    add(dp[i][j][k][2], mul(dp[i - 1][j + 1][k - x * dif[i]][2], y));
                    add(dp[i][j][k][2], dp[i - 1][j - 1][k - x * dif[i]][2]);
                    add(dp[i][j][k][2], mul(dp[i - 1][j][k - x * dif[i]][1], j - 1));
                    add(dp[i][j][k][2], dp[i - 1][j - 1][k - x * dif[i]][1]);
                    if (i == n && j == 1) {
                        add(dp[i][j][k][2], dp[i - 1][j + 1][k - x * dif[i]][2]);
                        add(dp[i][j][k][2], dp[i - 1][j][k - x * dif[i]][1]);
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int k = 0; k <= s; k++) add(ans, dp[n][1][k][2]);
    cout << ans << "\n";

    return 0;
}

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