Submission #1090755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090755		BF001	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	202 ms	199392 KiB

skyscraper

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

#define int long long
#define N 105
#define M 1005

int dp[3][N][N][M], n, l, a[N], md = 1e9 + 7;

void add(int& a, int b){
    a += b;
    if (a >= md) a -= md;
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> l;
    dp[0][0][0][0] = 1;

    if (n == 1){
        cout << 1;
        return 0;
    }

    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
  
    sort(a + 1, a + n + 1);
    a[n + 1] = 1e9;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            for (int typ = 0; typ <= 2; typ++){
                int cst = (a[i + 1] - a[i]) * (2 * j - typ);
                for (int s = cst; s <= l; s++){
                    add(dp[typ][i][j][s], dp[typ][i - 1][j - 1][s - cst]);
                    add(dp[typ][i][j][s], dp[typ][i - 1][j][s - cst] * (2 * j - typ) % md);
                    if (typ) add(dp[typ][i][j][s], dp[typ - 1][i - 1][j - 1][s - cst] * (3 - typ) % md);
                    else{
                        add(dp[typ][i][j][s], dp[typ][i - 1][j + 1][s - cst] * j % md * (j + 1) % md);
                    }
                    if (typ == 1){
                        add(dp[typ][i][j][s], dp[typ - 1][i - 1][j][s - cst] * 2 * j % md);
                        add(dp[typ][i][j][s], dp[typ][i - 1][j + 1][s - cst] * j % md * j % md);
                    }
                    if (typ == 2){
                        if (i != n) add(dp[typ][i][j][s], dp[typ][i - 1][j + 1][s - cst] * j % md * (j - 1) % md);
                        if (i == n) 
                        {
                            add(dp[typ][i][j][s], dp[typ][i - 1][j + 1][s - cst]);
                            add(dp[typ][i][j][s], dp[typ - 1][i - 1][j][s - cst]);
                        }
                        else 
                            add(dp[typ][i][j][s], dp[typ - 1][i - 1][j][s - cst] * (j - 1) % md);
                    }
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i <= l; i++) add(res, dp[2][n][1][i]);
    
    cout << res;

    return 0;
}

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