제출 #515968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515968		amunduzbaev	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	539 ms	99704 KiB

skyscraper

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

#define ar array

const int mod = 1e9 + 7;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, l; cin>>n>>l;
	vector<vector<vector<int>>> dp(1 << n, vector<vector<int>>(n, vector<int>(l + 1)));
	vector<int> a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a.begin(), a.end());
	for(int i=0;i<n;i++){
		dp[(1 << i)][i][0] = 1;
	}
	
	for(int mask=0;mask < (1 << n);mask++){
		for(int c=0;c<l;c++){
			for(int i=0;i<n;i++){
				if(!(mask >> i & 1)) continue;
				for(int j=0;j<n;j++){
					if(mask >> j & 1) continue;
					if(abs(a[i] - a[j]) + c > l) continue;
					int tm = mask | (1 << j);
					dp[tm][j][c + abs(a[i] - a[j])] = (dp[tm][j][c + abs(a[i] - a[j])] + dp[mask][i][c]) % mod;
				}
			}
		}
	}
	
	int res = 0;
	for(int c=0;c<=l;c++){
		for(int i=0;i<n;i++){
			res = (res + dp[(1 << n) - 1][i][c]) % mod;
		}
	}
	
	cout<<res<<"\n";
}

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