제출 #1149876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149876		dragst	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	153 ms	79564 KiB

skyscraper

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

const long long inf=1e12, mod=1e9+7;
long long a[105], dp[105][105][1005][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, l, i, j, k, num, ans=0;
    cin >> n >> l;
    for (i=1; i<=n; i++)
    {
        cin >> a[i];
    };
    sort(a+1, a+n+1);
    num=a[2]-a[1];
    if (num<=l) {dp[1][1][num][1]=2;};
    if (num*2<=l) {dp[1][1][num*2][0]=1;};
    for (i=1; i<n; i++)
    {
        if (i<n-1) {num=a[i+2]-a[i+1];}
        else {num=0;};
        for (j=1; j<=i; j++)
        {
            for (k=0; k<=l; k++)
            {
                if (j>1 && k+num*(j*2-4)<=l)
                {
                    if (i==n-1)
                    {
                        dp[i+1][j-1][k+num*(j*2-4)][2]+=dp[i][j][k][2];
                        dp[i+1][j-1][k+num*(j*2-4)][2]%=mod;
                    }
                    else
                    {
                        dp[i+1][j-1][k+num*(j*2-4)][2]+=((dp[i][j][k][2]*(j-2))%mod*(j-1))%mod;
                        dp[i+1][j-1][k+num*(j*2-4)][2]%=mod;
                    };
                };
                if (j>1&& k+num*(j*2-3)<=l)
                {
                    dp[i+1][j-1][k+num*(j*2-3)][1]+=((dp[i][j][k][1]*(j-1))%mod*(j-1))%mod;
                    dp[i+1][j-1][k+num*(j*2-3)][1]%=mod;
                };
                if (k+num*(j*2-2)<=l)
                {
                    if (j>1)
                    {
                        dp[i+1][j-1][k+num*(j*2-2)][0]+=((dp[i][j][k][0]*(j-1))%mod*j)%mod;
                        dp[i+1][j-1][k+num*(j*2-2)][0]%=mod;
                    };
                    dp[i+1][j][k+num*(j*2-2)][2]+=((dp[i][j][k][2]*2)%mod*(j-1))%mod;
                    dp[i+1][j][k+num*(j*2-2)][2]%=mod;
                    if (i==n-1)
                    {
                        dp[i+1][j][k+num*(j*2-2)][2]+=dp[i][j][k][1];
                        dp[i+1][j][k+num*(j*2-2)][2]%=mod;
                    }
                    else
                    {
                        dp[i+1][j][k+num*(j*2-2)][2]+=(dp[i][j][k][1]*(j-1))%mod;
                        dp[i+1][j][k+num*(j*2-2)][2]%=mod;
                    };
                };
                if (k+num*(j*2-1)<=l)
                {
                    dp[i+1][j][k+num*(j*2-1)][1]+=((dp[i][j][k][0]*2)%mod*j)%mod;
                    dp[i+1][j][k+num*(j*2-1)][1]%=mod;
                    dp[i+1][j][k+num*(j*2-1)][1]+=(dp[i][j][k][1]*(2*j-1))%mod;
                    dp[i+1][j][k+num*(j*2-1)][1]%=mod;
                };
                if (k+num*j*2<=l)
                {
                    dp[i+1][j][k+num*j*2][0]+=((dp[i][j][k][0]*2)%mod*j)%mod;
                    dp[i+1][j][k+num*j*2][0]%=mod;
                    dp[i+1][j+1][k+num*j*2][2]+=dp[i][j][k][1]%mod;
                    dp[i+1][j+1][k+num*j*2][2]%=mod;
                    dp[i+1][j+1][k+num*j*2][2]+=dp[i][j][k][2];
                    dp[i+1][j+1][k+num*j*2][2]%=mod;
                };
                if (k+num*(j*2+1)<=l)
                {
                    dp[i+1][j+1][k+num*(j*2+1)][1]+=(dp[i][j][k][0]*2)%mod;
                    dp[i+1][j+1][k+num*(j*2+1)][1]%=mod;
                    dp[i+1][j+1][k+num*(j*2+1)][1]+=dp[i][j][k][1];
                    dp[i+1][j+1][k+num*(j*2+1)][1]%=mod;
                };
                if (k+num*(j*2+2)<=l)
                {
                    dp[i+1][j+1][k+num*(j*2+2)][0]+=dp[i][j][k][0];
                    dp[i+1][j+1][k+num*(j*2+2)][0]%=mod;
                };
            };
        };
    };
    for (i=0; i<=l; i++) {ans+=dp[n][1][i][2]; ans%=mod;};
    if (n==1) {ans=1;};
    cout << ans;
}

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