Submission #1179462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179462		ngrace	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	1119 ms	550248 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define v vector
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define mp make_pair

const ll MOD = 1000000007;

int main(){
    int N,L;
    cin>>N>>L;
    v<ll> A(N);
    for(int i=0; i<N; i++) cin>>A[i];

    if(N<=8){
        sort(A.begin(),A.end());
        ll out=0;
        do{
            int tmp=0;
            for(int i=0; i<N-1; i++) tmp+=abs(A[i]-A[i+1]);
            if(tmp<=L) out++;
        }while(next_permutation(A.begin(),A.end()));
        cout<<out%MOD<<endl;
    }
    else if(N<=14){
        v<v<v<ll>>> dp(1<<N, v<v<ll>>(N,v<ll>(L+1,0)));
        for(int i=0; i<N; i++) dp[1<<i][i][0]=1;
        for(int tot=0; tot<=L; tot++){
            for(int mask=0; mask<(1<<N); mask++){
                for(int i=0; i<N; i++){
                    if((mask&(1<<i))==0) continue;
                    int newmask = (mask ^ (1<<i));
                    for(int j=0; j<N; j++){
                        if((newmask&(1<<j))==0) continue;
                        if(abs(A[i]-A[j])<=tot){
                            dp[mask][i][tot] += dp[newmask][j][tot-abs(A[i]-A[j])];
                            dp[mask][i][tot] = dp[mask][i][tot]%MOD;
                        }
                    }
                    //cout<<mask<<" "<<i<<" "<<tot<<" "<<dp[mask][i][tot]<<endl;
                }
            }
        }
        ll out=0;
        for(int tot=0; tot<=L; tot++){
            for(int i=0; i<N; i++) out = (out+dp[(1<<N)-1][i][tot])%MOD;
        }
        cout<<out<<endl;
    }
    else{
        sort(A.begin(),A.end());
        A.push_back(1001);
        v<v<v<v<ll>>>> dp(N,v<v<v<ll>>>(N+1,v<v<ll>>(L+1,v<ll>(3,0))));
        if(2*(A[1]-A[0])<=L) dp[0][1][2*(A[1]-A[0])][0]=1;
        if(A[1]-A[0]<=L) dp[0][1][A[1]-A[0]][1]=2;
        if(N==1) dp[0][1][0][2]=1;
        for(int tot=0; tot<=L; tot++){
            for(int e=0; e<=2; e++){
                for(int i=1; i<N; i++){
                    for(int j=1; j<=i+1; j++){
                        ll inc = (2*j-e)*(A[i+1]-A[i]);
                        if(inc>tot || i+1+j+1-e > N) continue;
                        //insert i as new component
                        dp[i][j][tot][e] += dp[i-1][j-1][tot-inc][e];
                        //insert i as new component at an endpoint
                        if(e>0) dp[i][j][tot][e] += (2-(e-1))*dp[i-1][j-1][tot-inc][e-1];

                        //append i to an existing component (not on end)
                        dp[i][j][tot][e] += (2*j-e)*dp[i-1][j][tot-inc][e];
                        //append i to a component such that i is on end
                        if(e==1) dp[i][j][tot][e] += (2*j)*dp[i-1][j][tot-inc][e-1];
                        if(e==2 && j==1){
                            if(i==N-1) dp[i][j][tot][e] += dp[i-1][j][tot-inc][e-1];
                        }
                        else if(e==2 && j>1) dp[i][j][tot][e] += (j-1) * dp[i-1][j][tot-inc][e-1];

                        //join to components with i
                        if(e==2 && i==N-1){
                            if(j==1) dp[i][j][tot][e] += dp[i-1][j+1][tot-inc][e];
                        }
                        else if(e==2) dp[i][j][tot][e] += j*(j-1)*dp[i-1][j+1][tot-inc][e];//(j+1)-1 choices of left, (j+1)-2 choice of right.
                        else if(e==1) dp[i][j][tot][e] += j*j*dp[i-1][j+1][tot-inc][e];//(j+1)j ordered pairs, exclude the j with the endpoint component on the wrong side
                        else dp[i][j][tot][e] += (j+1)*j*dp[i-1][j+1][tot-inc][e];

                        dp[i][j][tot][e] = dp[i][j][tot][e] % MOD;
                    }
                }
            }
        }

        ll out=0;
        for(int i=0; i<=L; i++) out = (out+dp[N-1][1][i][2])%MOD;
        cout<<out<<endl;
    }
}

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