Submission #961605

#	Time	Username	Problem	Language	Result	Execution time	Memory
961605		Unforgettablepl	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	410 ms	181740 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int modulo = 1e9+7;

int DP[16384][101][14];

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,l;
    cin >> n >> l;
    vector<int> arr(n);
    for(int&i:arr)cin>>i;
    for(int bitmask=0;bitmask<(1<<n);bitmask++){
        for(int currlen=0;currlen<=l;currlen++){
            for(int last=0;last<n;last++){
                if((bitmask&(1<<last))==0)continue;
                if(bitmask==(1<<last)){DP[bitmask][currlen][last]=1;continue;}
                int lastmask = bitmask^(1<<last);
                for(int bit=0;bit<n;bit++){
                    if(lastmask&(1<<bit)){
                        if(abs(arr[last]-arr[bit])<=currlen)DP[bitmask][currlen][last]+=DP[lastmask][currlen-abs(arr[last]-arr[bit])][bit];
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        ans+=DP[(1<<n)-1][l][i];
        ans%=modulo;
    }
    cout << ans << '\n';
}

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