제출 #1326550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326550		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 MOD = 1e9 + 7;
long long dp[101][101][1001][3];

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(10000); // Dummy qiymat chekka holat uchun
    dp[0][0][0][0] = 1;

    for (int i = 0; i < N; i++) {
        int diff = A[i + 1] - A[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 + diff * (2 * j - e);
                    if (next_k > L) continue;

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

                    // 1. Yangi blok yaratish (hech biriga ulanmaydi)
                    // Chekka bo'lmagan joyga
                    if (j + 1 <= N) dp[i+1][j+1][next_k][e] = (dp[i+1][j+1][next_k][e] + val * (j + 1 - e)) % MOD;
                    // Chekkaga
                    if (e < 2 && j + 1 <= N) dp[i+1][j+1][next_k][e+1] = (dp[i+1][j+1][next_k][e+1] + val * (2 - e)) % MOD;

                    // 2. Mavjud bloklardan biriga biriktirish (bir uchi yopiladi)
                    if (j > 0) {
                        // Chekka bo'lmagan joyga
                        dp[i+1][j][next_k][e] = (dp[i+1][j][next_k][e] + val * (2 * j - e)) % MOD;
                        // Chekkaga
                        if (e < 2) dp[i+1][j][next_k][e+1] = (dp[i+1][j][next_k][e+1] + val * (2 - e)) % MOD;
                    }

                    // 3. Ikkita blokni birlashtirish
                    if (j >= 2) {
                        dp[i+1][j-1][next_k][e] = (dp[i+1][j-1][next_k][e] + val * (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