Submission #1169276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169276		Warinchai	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	324 ms	129020 KiB

skyscraper

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>h;
int dp[105][105][1005][5];
int md=1e9+7;
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,l;cin>>n>>l;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        h.push_back(a);
    }
    h.push_back(0);
    sort(h.begin(),h.end());
    dp[0][0][0][0]=1;
    dp[1][1][0][0]=1;
    dp[1][1][0][1]=2;
    for(int i=1;i<n;i++){
        for(int j=1;j<=i;j++){
            for(int k=0;k<=l;k++){
                for(int m=0;m<3;m++){
                    int cost=k+(h[i+1]-h[i])*(2*j-m);
                    if(cost>l)continue;
                    //add middle component
                    dp[i+1][j+1][cost][m]+=(dp[i][j][k][m]*(j-m+1))%md;
                    dp[i+1][j+1][cost][m]%=md;
                    //add end component
                    dp[i+1][j+1][cost][m+1]+=(dp[i][j][k][m]*(2-m))%md;
                    dp[i+1][j+1][cost][m+1]%=md;
                    //append to component in middle
                    dp[i+1][j][cost][m]+=(dp[i][j][k][m]*(2*j-m))%md;
                    dp[i+1][j][cost][m]%=md;
                    //append to component at end
                    dp[i+1][j][cost][m+1]+=(dp[i][j][k][m]*(2-m))%md;
                    dp[i+1][j][cost][m+1]%=md;
                    //merge component
                    dp[i+1][j-1][cost][m]+=(dp[i][j][k][m]*(j-1))%md;
                    dp[i+1][j-1][cost][m]%=md;
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=l;i++)ans+=dp[n][1][i][2],ans%=md;
    if(n==1)ans++;
    cout<<ans;
}

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