Submission #1010332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010332		tvladm2009	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	510 ms	210256 KiB

skyscraper

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N = 100 + 7;
const int L = 2000 + 7; 
const int M = 1e9 + 7;

int n, l, a[N];
int dp[N][N][L][2][2];

int add(int a, int b) {
    a += b;
    if (a >= M) a -= M;
    if (a < 0) a += M;
    return a;
}

void addup(int &a, int b) {
    a = add(a, b);
}

int mul(int a, int b) {
    return (ll) a * b % M;
}

int mul(int a, int b, int c) {
    return mul(a, mul(b, c));
}

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

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