Submission #1173306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173306		irmuun	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	146 ms	260632 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll mod=1e9+7;

ll dp[105][105][1005][3];

void add(ll &a,ll b){
    b%=mod;
    a+=b;
    if(a>=mod) a-=mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,L;
    cin>>n>>L;
    ll a[n+5];
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    if(n==1){
        cout<<1;
        return 0;
    }
    sort(a,a+n);
    const ll inf=1e4;
    a[n]=inf;
    memset(dp,0,sizeof dp);
    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;
    }
    for(ll i=1;i<n;i++){
        ll dif=a[i+1]-a[i];
        for(ll j=1;j<=i;j++){
            for(ll k=0;k<=L;k++){
                for(ll z=0;z<=2;z++){
                    if(dp[i][j][k][z]==0) continue;
                    //one of the end
                    if(z<2&&k+dif*(2*j-z-1)<=L){
                        if(i==n-1){
                            add(dp[i+1][j][k+dif*(2*j-z-1)][z+1],dp[i][j][k][z]*(2-z)*j);
                        }
                        else if(z==0||j>1){//holbogdono
                            add(dp[i+1][j][k+dif*(2*j-z-1)][z+1],dp[i][j][k][z]*(2-z)*(j-z));
                        }
                        if(k+dif*(2*j-z+1)<=L){//holbogdohgui
                            add(dp[i+1][j+1][k+dif*(2*j-z+1)][z+1],dp[i][j][k][z]*(2-z));
                        }
                    }
                    //shine heseg
                    if(k+dif*(2*j-z+2)<=L){
                        add(dp[i+1][j+1][k+dif*(2*j-z+2)][z],dp[i][j][k][z]);
                    }
                    //ali neg hesegtei niilne
                    if(k+dif*(2*j-z)<=L){
                        add(dp[i+1][j][k+dif*(2*j-z)][z],dp[i][j][k][z]*(2*j-z));
                    }
                    //2 heseg holbono
                    if(k+dif*(2*j-z-2)<=L&&j>=2&&(i==n-1||j>2||z<2)){
                        if(z==0){
                            add(dp[i+1][j-1][k+dif*(2*j-z-2)][z],dp[i][j][k][z]*j*(j-1));
                        }
                        if(z==1){
                            add(dp[i+1][j-1][k+dif*(2*j-z-2)][z],dp[i][j][k][z]*(j-1)*(j-1));
                        }
                        if(z==2){
                            if(i==n-1){
                                add(dp[i+1][j-1][k+dif*(2*j-z-2)][z],dp[i][j][k][z]);
                            }
                            else{
                                add(dp[i+1][j-1][k+dif*(2*j-z-2)][z],dp[i][j][k][z]*(j-1)*(j-2));
                            }
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    for(ll k=0;k<=L;k++){
        add(ans,dp[n][1][k][2]);
    }
    cout<<ans;
}

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