Submission #343263

#TimeUsernameProblemLanguageResultExecution timeMemory
343263sinamhdvSkyscraper (JOI16_skyscraper)C++11
15 / 100
779 ms214636 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 1000 * 1000 * 1000; const ll LINF = (ll)INF * INF; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod) #define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod) #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 16 #define MAXL 110 ll dp[1 << MAXN][MAXN][MAXL]; int n, L; int a[MAXN]; int32_t main(void) { fast_io; cin >> n >> L; FOR(i, 0, n) cin >> a[i]; FOR(i, 0, n) { dp[1 << i][i][0] = 1; } FOR(mask, 1, 1 << n) { if (__builtin_popcount(mask) == 1) continue; FOR(l, 0, L + 1) { FOR(i, 0, n) { if (!(mask & (1 << i))) continue; int nmask = mask ^ (1 << i); FOR(j, 0, n) { if (!(nmask & (1 << j)) || abs(a[i] - a[j]) > l) continue; dp[mask][i][l] = (dp[mask][i][l] + dp[nmask][j][l - abs(a[i] - a[j])]) % mod; } } } } ll ans = 0; FOR(i, 0, n) { FOR(j, 0, L + 1) { ans = (ans + dp[(1 << n) - 1][i][j]) % mod; } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...