oj.uz

답안 #393944

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393944 2021-04-25T02:15:20 Z KhaledFarhat Skyscraper (JOI16_skyscraper) C++14
100 / 100
 108 ms 20268 KB 
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
int dp[105][105][1005][4];

int Add(int x, int y) {
    return (x + y) % MOD;
}

void Increase(int& x, int y) {
    x = Add(x, y);
}

int Multiply(int x, int y) {
    return 1LL * x * y % MOD;
}

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

    int n, L;
    cin >> n >> L;

    vector<int> a(n + 1);

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

    sort(a.begin() + 1, a.end());

    dp[2][1][0][0] = (n > 2); // middle
    dp[2][1][0][1] = 1; // left
    dp[2][1][0][2] = 1; // right
    dp[2][1][0][3] = (n == 1); // both

    for (int i = 2; i <= n; ++i) {
        int delta = a[i] - a[i - 1];

        for (int components = 1; components < i; ++components) {
            for (int balance = 0; balance <= L; ++balance) {
                for (int flag = 0; flag <= 3; ++flag) {
                    if (dp[i][components][balance][flag] == 0) {
                        continue;
                    }

                    int totalBorders = components * 2 - (flag & 1) - ((flag & 2) > 0);

                    if ((flag & 1) == 0) {
                        // place at the left side of the first component
                        int newBalance = balance + totalBorders * delta;

                        if (newBalance <= L) {
                            Increase(dp[i + 1][components][newBalance][flag | 1], dp[i][components][balance][flag]);
                        }

                        // create a new component at the left side
                        newBalance = balance + totalBorders * delta;

                        if (newBalance <= L) {
                            Increase(dp[i + 1][components + 1][newBalance][flag | 1], dp[i][components][balance][flag]);
                        }
                    }

                    if ((flag & 2) == 0) {
                        // place at the right side of the last component
                        int newBalance = balance + totalBorders * delta;

                        if (newBalance <= L) {
                            Increase(dp[i + 1][components][newBalance][flag | 2], dp[i][components][balance][flag]);
                        }

                        // create a new component at the right side
                        newBalance = balance + totalBorders * delta;

                        if (newBalance <= L) {
                            Increase(dp[i + 1][components + 1][newBalance][flag | 2], dp[i][components][balance][flag]);
                        }
                    }

                    // create a new component
                    int newBalance = balance + totalBorders * delta;
                    int validPositions = (components + 1) - (flag & 1) - ((flag & 2) > 0);

                    if (newBalance <= L) {
                        Increase(dp[i + 1][components + 1][newBalance][flag], Multiply(validPositions, dp[i][components][balance][flag]));
                    }

                    // append to the left side of a component
                    newBalance = balance + totalBorders * delta;
                    validPositions = components - (flag & 1);

                    if (newBalance <= L) {
                        Increase(dp[i + 1][components][newBalance][flag], Multiply(validPositions, dp[i][components][balance][flag]));
                    }

                    // append to the right side of a component
                    newBalance = balance + totalBorders * delta;
                    validPositions = components - ((flag & 2) > 0);

                    if (newBalance <= L) {
                        Increase(dp[i + 1][components][newBalance][flag], Multiply(validPositions, dp[i][components][balance][flag]));
                    }

                    // merge two components
                    newBalance = balance + totalBorders * delta;
                    validPositions = components - 1;

                    if (newBalance <= L) {
                        Increase(dp[i + 1][components - 1][newBalance][flag], Multiply(validPositions, dp[i][components][balance][flag]));
                    }
                }
            }
        }
    }

    int answer = 0;

    for (int balance = 0; balance <= L; ++balance) {
        Increase(answer, dp[n + 1][1][balance][3]);
    }

    cout << answer;

    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 2 ms 1484 KB Output is correct
22 Correct 108 ms 20268 KB Output is correct
23 Correct 64 ms 8264 KB Output is correct
24 Correct 68 ms 11568 KB Output is correct
25 Correct 70 ms 9264 KB Output is correct
26 Correct 67 ms 8644 KB Output is correct
27 Correct 39 ms 9572 KB Output is correct
28 Correct 42 ms 11460 KB Output is correct
29 Correct 74 ms 15012 KB Output is correct
30 Correct 70 ms 9360 KB Output is correct