제출 #971954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971954		12345678	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	117 ms	86356 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=105, mx=1005, mod=1e9+7;

ll n, m, h[nx], dp[nx][nx][mx][3], res, c;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (ll i=1; i<=n; i++) cin>>h[i];
    if (n==1) return cout<<1, 0;
    sort(h+1, h+n+1);
    dp[0][0][0][0]=1;
    for (ll i=1; i<n; i++)
    {
        for (ll j=1; j<=i; j++)
        {
            for (ll k=0; k<=m; k++)
            {
                for (ll l=0; l<3; l++)
                {
                    ll x=(h[i+1]-h[i])*(2*j-l);
                    if (k<x) continue;
                    dp[i][j][k][l]=dp[i-1][j-1][k-x][l];
                    if (l>0) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j-1][k-x][l-1]*(3-l))%mod;
                    dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j][k-x][l]*(2*j-l))%mod;
                    if (l>0) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j][k-x][l-1]*(3-l)*(j-(l-1)))%mod;
                    if (l==0) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j+1][k-x][l]*(j+1)*j)%mod;
                    if (l==1) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j+1][k-x][l]*j*j)%mod;
                    if (l==2) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j+1][k-x][l]*j*(j-1))%mod;
                }
            }
        }
    }
    for (ll i=0; i<=m; i++) res=(res+dp[n-1][2][i][2]+dp[n-1][1][i][1])%mod;
    cout<<res;
}

/*
4 2
1 2 3 4
*/

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