제출 #1243143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243143		skibidihehe	Skyscraper (JOI16_skyscraper)	C++20	0 / 100	1 ms	580 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const ll MOD = 1e9 + 7;

ll dp[102][102][1001][3];
ll a[102];

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

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

    // Trường hợp đặc biệt chỉ có một phần tử
    if (n == 1) {
        cout << 1;
        return 0;
    }

    a[n + 1] = 10000; // Giá trị vô cực để đơn giản hoá xử lý

    // Khởi tạo dp cho hai phần tử đầu tiên
    int diff = a[2] - a[1];
    if (diff <= l)
        dp[1][1][diff][1] = 2;  // Điền a[1] vào một đầu mút, có 2 cách
    if (2 * diff <= l)
        dp[1][1][2 * diff][0] = 1; // Điền a[1] ở giữa, vị trí không phân biệt

    // DP tổng quát cho i = 1..n
    for (int i = 1; i <= n; i++) {
        diff = a[i + 1] - a[i];
        for (int j = 1; j <= i; j++) {
            for (int k = 0; k <= l; k++) {
                for (int z = 0; z < 3; z++) {
                    if (!dp[i][j][k][z]) continue;
                    ll cur = dp[i][j][k][z];

                    // 1) Thêm phần tử vào một đầu mút
                    if (z < 2 && k + diff * (2 * j - z - 1) <= l) {
                        // Gắn vào một component hiện có hoặc tạo component mới
                        if (i == n) {
                            dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1] = 
                                (dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1] + cur * (2 - z)) % MOD;
                        } else if (j - z) {
                            dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1] = 
                                (dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1] + cur * (2 - z) * (j - z)) % MOD;
                        }
                        // Tạo component mới tại đầu
                        if (k + diff * (2 * j - z + 1) <= l) {
                            dp[i + 1][j + 1][k + diff * (2 * j - z + 1)][z + 1] = 
                                (dp[i + 1][j + 1][k + diff * (2 * j - z + 1)][z + 1] + cur * (2 - z)) % MOD;
                        }
                    }

                    // 2) Không điền vào đầu mút
                    // 2.1) Tạo component mới giữa
                    if (k + diff * (2 * j - z + 2) <= l) {
                        dp[i + 1][j + 1][k + diff * (2 * j - z + 2)][z] = 
                            (dp[i + 1][j + 1][k + diff * (2 * j - z + 2)][z] + cur) % MOD;
                    }
                    // 2.2) Gắn vào một component hiện có
                    if (k + diff * (2 * j - z) <= l) {
                        dp[i + 1][j][k + diff * (2 * j - z)][z] = 
                            (dp[i + 1][j][k + diff * (2 * j - z)][z] + cur * (2 * j - z)) % MOD;
                    }
                    // 2.3) Gộp hai component
                    if (k + diff * (2 * j - z - 2) <= l && j >= 2 && (i == n || j > 2 || z < 2)) {
                        if (z == 0) {
                            dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] = 
                                (dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] + cur * j * (j - 1)) % MOD;
                        }
                        if (z == 1) {
                            dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] = 
                                (dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] + cur * (j - 1) * (j - 1)) % MOD;
                        }
                        if (z == 2) {
                            if (i == n) {
                                dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] = 
                                    (dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] + cur) % MOD;
                            } else {
                                dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] = 
                                    (dp[i + 1][j - 1][k + diff * (2 * j - z - 2)][z] + cur * (j - 2) * (j - 1)) % MOD;
                            }
                        }
                    }
                }
            }
        }
    }

    // Tính kết quả: tổng số cách với đúng 1 component và lấp đầy 2 đầu mút
    ll answer = 0;
    for (int k = 0; k <= l; k++) {
        answer = (answer + dp[n][1][k][2]) % MOD;
    }
    cout << answer << '\n';
    return 0;
}

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