Submission #1085135

#TimeUsernameProblemLanguageResultExecution timeMemory
1085135anhthiSkyscraper (JOI16_skyscraper)C++14
100 / 100
42 ms832 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define mp(x, y) make_pair(x, y) #define sz(v) ((int) (v).size()) #define all(v) (v).begin(), (v).end() #define MASK(i) (1LL << (i)) #define BIT(x, y) (((x) >> (y)) & 1) #define pb push_back #define max_rng *max_element #define min_rng *min_element #define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i) #define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i) template <class X, class Y> inline bool maximize(X &x, Y y) { return (x < y ? x = y, true : false); } template <class X, class Y> inline bool minimize(X &x, Y y) { return (x > y ? x = y, true : false); } template <class X> inline void compress(vector<X> &a) { sort(all(a)); a.resize(unique(all(a)) - a.begin()); } int ctz(ll x) { return __builtin_ctzll(x); } int lg(ll x) { return 63 - __builtin_clzll(x); } int popcount(ll x) { return __builtin_popcount(x); } mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return l + abs((ll) rng()) % (r - l + 1); } const ll oo = (ll) 1e17; const int inf = (ll) 2e9 + 7, mod = (ll) 1e9 + 7; const int mxn = 1e2, mxm = 1e3; const int LG = 18, BASE = 311; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } void sub(int &x, int y) { x -= y; if (x < 0) x += mod; } int n, L; int a[mxn + 5]; int f[2][mxn + 5][mxm + 5][3]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> L; rep(i, n) cin >> a[i]; sort(a + 1, a + 1 + n); if (n == 1) return cout << 1 << '\n', 0; f[1][1][0][0] = 1; f[1][1][0][1] = 2; forn(i, 2, n) { forn(cc, 1, n) forn(sum, 0, L) forn(ends, 0, 2) { int &val = f[(i-1)&1][cc][sum][ends]; if (!val) continue; int new_sum = sum + 1LL * (2 * cc - ends) * (a[i] - a[i-1]); if (new_sum <= L) { { //add new component add(f[i & 1][cc + 1][new_sum][ends], 1LL * (cc + 1 - ends) * val % mod); add(f[i & 1][cc + 1][new_sum][ends + 1], 1LL * (2 - ends) * val % mod); } { // appends to components add(f[i & 1][cc][new_sum][ends], 1LL * (2 * cc - ends) * val % mod); add(f[i & 1][cc][new_sum][ends + 1], 1LL * (2 - ends) * val % mod); } { // merge two components add(f[i & 1][cc - 1][new_sum][ends], 1LL * (cc - 1) * val % mod); } } val = 0; } } int ans = 0; forn(sum, 0, L) add(ans, f[n & 1][1][sum][2]); cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...