답안 #660468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660468 2022-11-21T23:35:19 Z four_specks Skyscraper (JOI16_skyscraper) C++17
15 / 100
1 ms 468 KB
#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

const long MOD = 1'000'000'007;

void solve()
{
    int n;
    int l;
    cin >> n >> l;

    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    sort(a.begin(), a.end());

    vector dp(1, vector(l + 1, vector<long>(3, 0)));
    dp[0][0][0] = 1;
    for (int i = 0; i < n - 1; i++)
    {
        vector nxt_dp(i + 2, vector(l + 1, vector<long>(3, 0)));
        for (int j = 1; j <= i + 1; j++)
        {
            for (int x = 0; x <= l; x++)
            {
                for (int k = 0; k <= 2; k++)
                {
                    long cost = (2 * j - k) * (a[i + 1] - a[i]);
                    if (x >= cost)
                    {
                        // create new component w/o endpoint
                        nxt_dp[j][x][k] += (j - k) * dp[j - 1][x - cost][k];

                        // create new component w/ endpoint
                        if (k >= 1)
                            nxt_dp[j][x][k] += (3 - k) * dp[j - 1][x - cost][k - 1];

                        if (j <= i)
                        {
                            // add to component w/o endpoint
                            nxt_dp[j][x][k] += (2 * j - k) * dp[j][x - cost][k];

                            // add to component w/ endpoint
                            if (k >= 1)
                                nxt_dp[j][x][k] += (3 - k) * dp[j][x - cost][k - 1];
                        }

                        if (j < i)
                            // merge two components
                            nxt_dp[j][x][k] += j * dp[j + 1][x - cost][k];

                        nxt_dp[j][x][k] %= MOD;
                    }
                }
            }
        }

        dp = move(nxt_dp);
    }

    long cnt = 0;
    for (int x = 0; x <= l; x++)
        cnt += dp[1][x][1] + dp[2][x][2];
    cnt %= MOD;

    cout << cnt << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 444 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -