Submission #1013908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013908		Baytoro	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	43 ms	24104 KiB

skyscraper

//resolve it

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
const int N=105,mod=1e9+7;
int dp[N][N][1005][3];
void solve(){
    int n,l;cin>>n>>l;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    if(n==1) {
        cout<<1<<endl;
        return;
    }
    sort(all(a));
    if(a[1]-a[0]<=l) dp[1][1][a[1]-a[0]][1]=2;
    if(2*(a[1]-a[0])<=l) dp[1][1][2*(a[1]-a[0])][0]=1;
    a.pb(10000);
    for(int i=1;i<n;i++) {
        int d=(a[i+1]-a[i]);
        for(int j=1;j<=i;j++) {
            for(int s=0;s<=l;s++) {
                for(int f=0;f<3;f++) {
                    if(!dp[i][j][s][f]) continue;
                    //add to ends

                    if(f<2 && s+d*(2*j-f-1)<=l) {
                        if(i==n-1) {
                            dp[i+1][j][s+d*(2*j-f-1)][f+1]+=(dp[i][j][s][f]*(2-f)*j);
                            dp[i+1][j][s+d*(2*j-f-1)][f+1]%=mod;
                        }

                        else if(f==0 || j>1) {
                            dp[i+1][j][s+d*(2*j-f-1)][f+1]+=(dp[i][j][s][f]*(2-f)*(j-f));
                            dp[i+1][j][s+d*(2*j-f-1)][f+1]%=mod;
                        }

                        if(s+d*(2*j-f+1)<=l) {
                            dp[i+1][j+1][s+d*(2*j-f+1)][f+1]+=(dp[i][j][s][f]*(2-f));
                            dp[i+1][j+1][s+d*(2*j-f+1)][f+1]%=mod;
                        }
                    }
                    //create
                    if(s+d*(2*j-f+2)<=l) {
                        dp[i+1][j+1][s+d*(2*j-f+2)][f]+=dp[i][j][s][f];
                        dp[i+1][j+1][s+d*(2*j-f+2)][f]%=mod;
                    }

                    //add
                    if(s+d*(2*j-f)<=l) {//<-
                        dp[i+1][j][s+d*(2*j-f)][f]+=dp[i][j][s][f]*(2*j-f);
                        dp[i+1][j][s+d*(2*j-f)][f]%=mod;
                    }

                    //merge
                    if(s+d*(2*j-f-2)<=l && j>=2 && (i==n-1 || j>2 || f<2)) {
                        if(f==0) {
                            dp[i+1][j-1][s+d*(2*j-f-2)][f]+=dp[i][j][s][f]*(j-1)*j;
                            dp[i+1][j-1][s+d*(2*j-f-2)][f]%=mod;
                        }
                        if(f==1) {
                            dp[i+1][j-1][s+d*(2*j-f-2)][f]+=dp[i][j][s][f]*(j-1)*(j-1);
                            dp[i+1][j-1][s+d*(2*j-f-2)][f]%=mod;
                        }
                        if(f==2) {
                            if(i==n-1) {
                                dp[i+1][j-1][s+d*(2*j-f-2)][f]+=dp[i][j][s][f];
                                dp[i+1][j-1][s+d*(2*j-f-2)][f]%=mod;
                            }
                            else {
                                dp[i+1][j-1][s+d*(2*j-f-2)][f]+=dp[i][j][s][f]*(j-1)*(j-2);
                                dp[i+1][j-1][s+d*(2*j-f-2)][f]%=mod;
                            }
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=l;i++) {
        ans+=dp[n][1][i][2];
        ans%=mod;
    }
    cout<<ans<<endl;
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

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