Submission #1243137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243137		skibidihehe	Skyscraper (JOI16_skyscraper)	C++20	0 / 100	0 ms	580 KiB

skyscraper

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fi first
#define se second
#define pb push_back
#define taskname ""

const ll MOD = 1e9 + 7;

ll dp[105][105][1005][3];
ll a[105];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, L;
    cin >> n >> L;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    // Đặt giá trị "infinity" ở vị trí n+1 để tiện tính diff
    a[n + 1] = 10000;

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

    // Khởi tạo cho i = 2 (đã đặt a[1] và a[2])
    int diff0 = a[2] - a[1];
    if(diff0 <= L) dp[2][1][diff0][1] = 2;          // đặt a[1] vào một đầu, có 2 cách
    if(2 * diff0 <= L) dp[2][1][2 * diff0][0] = 1;  // đặt a[1] vào giữa, 1 cách

    // DP chuyển tiếp từ i đến i+1
    for(int i = 2; i < n; i++) {
        int diff = a[i + 1] - a[i];
        for(int j = 1; j <= i - 1; j++) {
            for(int cost = 0; cost <= L; cost++) {
                for(int z = 0; z < 3; z++) {
                    ll cur = dp[i][j][cost][z];
                    if(cur == 0) continue;

                    // 1) Chèn vào một đầu
                    if(z < 2) {
                        int upgrade = 2 * j - z - 1;
                        int newCost = cost + diff * upgrade;
                        if(newCost <= L) {
                            // gắn vào CC hiện tại
                            if(i + 1 == n) {
                                dp[i + 1][j][newCost][z + 1] = (dp[i + 1][j][newCost][z + 1] + cur * (2 - z)) % MOD;
                            } else if(j - z > 0) {
                                dp[i + 1][j][newCost][z + 1] = (dp[i + 1][j][newCost][z + 1] + cur * (2 - z) * (j - z)) % MOD;
                            }
                            // tạo CC mới
                            int upgradeNew = 2 * j - z + 1;
                            int costNewCC = cost + diff * upgradeNew;
                            if(costNewCC <= L) {
                                dp[i + 1][j + 1][costNewCC][z + 1] = (dp[i + 1][j + 1][costNewCC][z + 1] + cur * (2 - z)) % MOD;
                            }
                        }
                    }

                    // 2) Không chèn vào đầu
                    // 2.1 Tạo CC mới
                    {
                        int upgrade = 2 * j - z + 2;
                        int newCost = cost + diff * upgrade;
                        if(newCost <= L) {
                            dp[i + 1][j + 1][newCost][z] = (dp[i + 1][j + 1][newCost][z] + cur) % MOD;
                        }
                    }
                    // 2.2 Gắn vào một CC hiện hữu
                    {
                        int upgrade = 2 * j - z;
                        int newCost = cost + diff * upgrade;
                        if(newCost <= L) {
                            dp[i + 1][j][newCost][z] = (dp[i + 1][j][newCost][z] + cur * (2 * j - z)) % MOD;
                        }
                    }
                    // 2.3 Merge hai CC
                    if(j >= 2) {
                        int upgrade = 2 * j - z - 2;
                        int newCost = cost + diff * upgrade;
                        if(newCost <= L && (i + 1 == n || j > 2 || z < 2)) {
                            if(z == 0) {
                                dp[i + 1][j - 1][newCost][z] = (dp[i + 1][j - 1][newCost][z] + cur * j * (j - 1)) % MOD;
                            } else if(z == 1) {
                                dp[i + 1][j - 1][newCost][z] = (dp[i + 1][j - 1][newCost][z] + cur * (j - 1) * (j - 1)) % MOD;
                            } else {
                                if(i + 1 == n) {
                                    dp[i + 1][j - 1][newCost][z] = (dp[i + 1][j - 1][newCost][z] + cur) % MOD;
                                } else {
                                    dp[i + 1][j - 1][newCost][z] = (dp[i + 1][j - 1][newCost][z] + cur * (j - 2) * (j - 1)) % MOD;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    // Tính kết quả: còn đúng 1 CC, hai đầu đã lấp
    ll answer = 0;
    for(int cost = 0; cost <= L; cost++) {
        answer = (answer + dp[n][1][cost][2]) % MOD;
    }
    cout << answer << "\n";
    return 0;
}

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