Submission #380609

#	Time	Username	Problem	Language	Result	Execution time	Memory
380609		smjleo	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	100 ms	77292 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1000000007, mod2 = 998244353;

// change this
const int N = 105;
const int L = 1005;

int n, l, arr[N], dp[N][N][L][3];

signed main() {
    io;
    cin >> n >> l;
    for (int i=1; i<=n; i++) cin >> arr[i];

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

    sort(arr, arr+n+1);
    arr[n+1] = 1e9;

    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<=l; k++) {
                for (int m=0; m<3; m++) {
                    // i: index, j: components, k: sum, m: ends
                    int dc = (2*j-m) * (arr[i+1] - arr[i]);
                    // difference in cost. each component contributes 2*j except for the m ones which contribute 1

                    if (dc > k) continue;   // cost too much lol

                    // we can create a new component that isn't the end
                    dp[i][j][k][m] += dp[i-1][j-1][k-dc][m];

                    // we can create a new component that is the end
                    if (m) dp[i][j][k][m] += (3-m) * dp[i-1][j-1][k-dc][m-1];

                    // we can join an existing component but not combine
                    dp[i][j][k][m] += (2*j-m) * dp[i-1][j][k-dc][m];

                    // we can join two existing components [[...]X[...]]
                    if (m == 0) {
                        dp[i][j][k][m] += j*(j+1)*dp[i-1][j+1][k-dc][m];
                        // for each of the j+1 i can match with j
                    } else if (m == 1) {
                        dp[i][j][k][m] += j*j*dp[i-1][j+1][k-dc][m];
                        // for each of the j (because end cannot) i can match with j
                    } else {
                        if (i == n) dp[i][j][k][m] += dp[i-1][j+1][k-dc][m];
                        else dp[i][j][k][m] += j*(j-1)*dp[i-1][j+1][k-dc][m];
                        // for each of the j-1 (because ends cannot) i can match with j
                    }

                    // we can bring an existing component to the end
                    if (m == 1) {
                        dp[i][j][k][m] += (2*j) * dp[i-1][j][k-dc][m-1];    // 2j components to select from (two ends of each)
                    } else if (m == 2) {
                        if (i == n) dp[i][j][k][m] += dp[i-1][j][k-dc][m-1];    // only one thing to select from
                        else if (j) dp[i][j][k][m] += (j-1) * dp[i-1][j][k-dc][m-1];   // j-1 components to select from (one end of each except other end)
                    }

                    dp[i][j][k][m] %= mod;
                }       
            }
        }
    }
    int ans = 0;
    for (int i=0; i<=l; i++) {
        ans += dp[n][1][i][2];
        ans %= mod;
    }

    cout << ans << nl;
}

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