제출 #94599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94599		Bliss_of_comprehension	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	900 ms	316924 KiB

skyscraper

#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

typedef long long ll;

ll dp[105][105][1005][2][2]={};

int main(){
    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 0;
    }
    sort(a.begin(),a.end());
    dp[0][0][0][0][0]=1;
    ll ans=0;
    for(int i=0;i<n;i++){
        if(i==n-1){
            for(int k=0;k<=l;k++){
                for(int iss=0;iss<2;iss++){
                    for(int ise=0;ise<2;ise++){
                        dp[i][0][k][iss][ise]%=mod;
                        if(iss+ise>0)
                            ans=(ans+dp[i][0][k][iss][ise])%mod;
                    }
                }

            }
            continue;
        }

        for(int j=0;j<=n;j++){
            for(int k=0;k<=l;k++){
                for(int iss=0;iss<2;iss++){
                    for(int ise=0;ise<2;ise++){
//                        if(i==2){
//                            cout << i << " " << j << " " << k << " " << iss << " " << ise << " " << dp[i][j][k][iss][ise] << endl;
//                        }
                        ll &cur = dp[i][j][k][iss][ise];
                        assert(cur>=0);
                        cur%=mod;
                        int diff = a[i+1]-a[i];
                        int nl=k+(a[i+1]-a[i])*(2*j+iss+ise);
                        if(j){
                            if(nl-2*diff>l){
                                continue;
                            }
                            if(iss){
                                dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j;
                                dp[i+1][j-1][nl-2*diff][iss][ise]%=mod;
                            }
                            if(ise){
                                dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j;
                                dp[i+1][j-1][nl-2*diff][iss][ise]%=mod;
                            }
                            if(j>1){
                                dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j*(j-1);
                                dp[i+1][j-1][nl-2*diff][iss][ise]%=mod;
                            }
                            if(nl-diff>l){
                                continue;
                            }
                            if(!iss){
                                dp[i+1][j-1][nl-diff][1][ise]+=cur*j;
                                dp[i+1][j-1][nl-diff][1][ise]%=mod;
                            }
                            if(!ise){
                                dp[i+1][j-1][nl-diff][iss][1]+=cur*j;
                                dp[i+1][j-1][nl-diff][iss][1]%=mod;
                            }
                        }

                        if(nl>l){
                            continue;
                        }
                        if(iss){
                            dp[i+1][j][nl][iss][ise]+=cur;
                            dp[i+1][j][nl][iss][ise]%=mod;
                        }
                        if(ise){
                            dp[i+1][j][nl][iss][ise]+=cur;
                            dp[i+1][j][nl][iss][ise]%=mod;
                        }
                        if(j){
                            dp[i+1][j][nl][iss][ise]+=(2*j)*cur;
                            dp[i+1][j][nl][iss][ise]%=mod;
                        }
                        if(nl+diff>l){
                            continue;
                        }
                        if(!iss){
                            dp[i+1][j][nl+diff][1][ise]+=cur;
                            dp[i+1][j][nl+diff][1][ise]%=mod;
                        }
                        if(!ise){
                            dp[i+1][j][nl+diff][iss][1]+=cur;
                            dp[i+1][j][nl+diff][iss][1]%=mod;
                        }
                        if(nl+2*diff>l){
                            continue;
                        }
                        dp[i+1][j+1][nl+2*diff][iss][ise]+=cur;
                        dp[i+1][j+1][nl+2*diff][iss][ise]%=mod;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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