Submission #1362782

#TimeUsernameProblemLanguageResultExecution timeMemory
1362782warrennSkyscraper (JOI16_skyscraper)C++20
15 / 100
0 ms580 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=1e9+7;
int dp[102][102][3][102];

void add(int &a,int b){
    a+=b; a%=mod;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,l;
    cin>>n>>l;
    int a[n+1];
    for(int q=1;q<=n;q++){
        cin>>a[q];
    }
    sort(a+1,a+n+1);

    dp[1][1][0][0]=1; dp[1][1][1][0]=2; dp[1][1][2][0]=1;
    for(int q=1;q<n;q++){
        for(int w=1;w<=q;w++){
            for(int e=0;e<3;e++){
                int cost=(2*w-e)*(a[q+1]-a[q]);
                for(int r=cost;r<=l;r++){
                    // gabung cc
                    add(dp[q+1][w-1][e][r],dp[q][w][e][r-cost]*(w-1));
                    // tepi cc
                    add(dp[q+1][w][e][r],dp[q][w][e][r-cost]*(2*w-e));
                    add(dp[q+1][w][e+1][r],dp[q][w][e][r-cost]*(2-e));
                    // nambah cc
                    add(dp[q+1][w+1][e][r],dp[q][w][e][r-cost]*(w+1-e));
                    add(dp[q+1][w+1][e+1][r],dp[q][w][e][r-cost]*(2-e));
                }
            }
        }
    }
    int ans=0;
    for(int q=0;q<=l;q++){
        add(ans,dp[n][1][2][q]);
    }
    cout<<ans<<endl;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...