제출 #1326300

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

skyscraper

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long dp[105][105][1005][3];
const int MOD = 1000000007;

int main() {
    int N, L;
    cin >> N >> L;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

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

    A.push_back(2000); // Guard value
    dp[0][0][0][0] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= L; k++) {
                for (int e = 0; e <= 2; e++) {
                    if (!dp[i][j][k][e]) continue;

                    int next_k = k + (A[i+1] - A[i]) * (2 * j - e);
                    if (next_k > L) continue;

                    long long cur = dp[i][j][k][e];

                    // 1. Yangi komponent yaratish
                    // Chekkaga qo'ymaslik
                    if (j + 1 <= N)
                        dp[i+1][j+1][next_k][e] = (dp[i+1][j+1][next_k][e] + cur * (j + 1 - e)) % MOD;
                    // Chekkaga qo'yish
                    if (e < 2)
                        dp[i+1][j+1][next_k][e+1] = (dp[i+1][j+1][next_k][e+1] + cur * (2 - e)) % MOD;

                    // 2. Mavjud komponentga qo'shish
                    if (j > 0) {
                        // Bir chekkasiga ulanish
                        dp[i+1][j][next_k][e] = (dp[i+1][j][next_k][e] + cur * (2 * j - e)) % MOD;
                        // Chekkaga ulanish
                        if (e < 2)
                            dp[i+1][j][next_k][e+1] = (dp[i+1][j][next_k][e+1] + cur * (2 - e)) % MOD;
                    }

                    // 3. Ikkita komponentni birlashtirish
                    if (j >= 2) {
                        // Oxirgi qadamda hammasini bitta qilish
                        if (i == N - 1 && j == 2 && e == 2) { /* maxsus holat pastda */ }
                        dp[i+1][j-1][next_k][e] = (dp[i+1][j-1][next_k][e] + cur * (j - 1)) % MOD;
                    }
                }
            }
        }
    }

    long long ans = 0;
    for (int k = 0; k <= L; k++) {
        ans = (ans + dp[N][1][k][2]) % MOD;
    }
    cout << ans << endl;

    return 0;
}

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