Submission #1124733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124733		nguyenkhangninh99	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	374 ms	197416 KiB

skyscraper

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

#define int long long

const int maxn = 14, maxs = 1e2 + 5, mod = 1e9 + 7;
int dp[(1 << maxn) + 5][maxn + 1][maxs];


void solve(){
	int n, s; cin >> n >> s;

	vector<int> h(n + 1);
    for(int i = 1; i <= n; i++) cin >> h[i];
    
	if(n <= 8){
		int ans = 0;
        vector<int> p(n + 1);
		for(int i = 1; i <= n; i++) p[i] = i;
        do {
            int x = 0;
            for(int i = 1; i < n; i++) x += abs(h[p[i]] - h[p[i + 1]]);
            if(x <= s) ans++;
        } while(next_permutation(p.begin() + 1, p.end()));
        cout << ans;
	}

	else{
		for(int i = 1; i <= n; i++) dp[1 << (i - 1)][i][0] = 1;
		for(int mask = 1; mask < (1 << n); mask++) {
			for(int i = 1; i <= n; i++) {
				if((mask >> (i - 1)) & 1){
					for(int j = 1; j <= n; j++) {
						if(i != j){
							int x = abs(h[i] - h[j]), lst = mask ^ (1 << (i - 1));
							for(int k = s; k >= x; k--){
								dp[mask][i][k] += dp[lst][j][k - x];
								dp[mask][i][k] %= mod;
							}
						}
					}
				}
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 0; j <= s; j++) ans = (ans + dp[(1 << n) - 1][i][j]) % mod;
		}

		cout << ans << "\n";
	}
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
	solve();
}

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