제출 #947708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947708		chroot_	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	475 ms	192088 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

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

const int N = 105, V = 3005;
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] = 2004;
    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; 
}

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