Submission #947705

# Submission time Handle Problem Language Result Execution time Memory
947705 2024-03-16T22:23:02 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
15 / 100
4 ms 4956 KB
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using PII = pair<int, int>;

const int N = 105, V = 1005;
const int M = 1e9 + 7;

LL dp[N][N][V][2][2], a[N];

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 + 1 + n), a[n + 1] = V * 2;
    int d = a[2] - a[1];

    dp[1][1][0][0][0] = 1, dp[1][1][d][1][0] = 1;
    dp[1][1][d][0][1] = 1, dp[1][1][d * 2][1][1] = 1;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            for(int sum = 0; sum <= L; sum++) {
                for(int l = 0; l <= 1; l++) {
                    for(int r = 0; r <= 1; r++) {

                        // place a new component in the middle
                        int new_sum = sum + (j * 2 + l + r) * (a[i + 2] - a[i + 1]);
                        dp[i + 1][j + 1][new_sum][l][r] += dp[i][j][sum][l][r] * (j - 1) % M;
                        dp[i + 1][j + 1][new_sum][l][r] %= M;

                        //place a new component in the left , don't block it
                        if(l > 0){
                            new_sum = sum + (j * 2 + l + r) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j + 1][new_sum][l][r] += dp[i][j][sum][l][r];
                            dp[i + 1][j + 1][new_sum][l][r] %= M;
                        }

                        //place a new component in the left and block it
                        if(l > 0){
                            new_sum = sum + (j * 2 + r) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j + 1][new_sum][0][r] += dp[i][j][sum][l][r];
                            dp[i + 1][j + 1][new_sum][0][r] %= M;
                        }

                        //place a new component in the right, don't block it
                        if(r > 0){
                            new_sum = sum + (j * 2 + l + r) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j + 1][new_sum][l][r] += dp[i][j][sum][l][r];
                            dp[i + 1][j + 1][new_sum][l][r] %= M;
                        }

                        //place a new component in the right and block it
                        if(r > 0){
                            new_sum = sum + (j * 2 + l) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j + 1][new_sum][l][0] += dp[i][j][sum][l][r];
                            dp[i + 1][j + 1][new_sum][l][0] %= M;
                        }

                        //add to existing component but not at the end of permutation
                        new_sum = sum + ((j - 1) * 2  + l + r) * (a[i + 2] - a[i + 1]);
                        dp[i + 1][j][new_sum][l][r] += dp[i][j][sum][l][r] * (j - 1 ) * 2 % M;
                        dp[i + 1][j][new_sum][l][r] %= M;

                        //adding to left of the leftmost component but do not block it
                        if(l > 0){
                            new_sum = sum + ((j - 1) * 2  + l + r) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j][new_sum][l][r] += dp[i][j][sum][l][r];
                            dp[i + 1][j][new_sum][l][r] %= M;
                        }

                        //adding to left of the leftmost component and block it
                        if(l > 0){
                            new_sum = sum + ((j - 1) * 2  + l + r - 1) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j][new_sum][0][r] += dp[i][j][sum][l][r];
                            dp[i + 1][j][new_sum][0][r] %= M;
                        }

                        //adding to right of the rightmost component but do not block it
                        if(r > 0){
                            new_sum = sum + ((j - 1) * 2  + l + r) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j][new_sum][l][r] += dp[i][j][sum][l][r];
                            dp[i + 1][j][new_sum][l][r] %= M;
                        }

                        //adding to right of the rightmost component and block it
                        if(r > 0){
                            new_sum = sum + ((j - 1) * 2  + l + r - 1) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j][new_sum][l][0] += dp[i][j][sum][l][r];
                            dp[i + 1][j][new_sum][l][0] %= M;
                        }

                        //merging two components
                        if(j > 1 ) {
                            new_sum = sum + ((j - 2 ) * 2 + l + r) * (a[i + 2] - a[i + 1]);
                            dp[i + 1][j - 1][new_sum][l][r] += dp[i][j][sum][l][r] * (j - 1)%M;
                            dp[i + 1][j - 1][new_sum][l][r] %= M;
                        }

                    }
                }
            }
        }
    }

    LL ans = 0;
    for(int sum = 0; sum <= L; sum++) ans = (ans + dp[n][1][sum][0][0]) % M;
    cout << ans <<"\n"; 
}

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 4 ms 4956 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 1 ms 3416 KB Output is correct
4 Correct 2 ms 3672 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 2 ms 3420 KB Output is correct
9 Correct 2 ms 3688 KB Output is correct
10 Correct 2 ms 3676 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Incorrect 4 ms 4956 KB Output isn't correct
6 Halted 0 ms 0 KB -