Submission #1026556

#TimeUsernameProblemLanguageResultExecution timeMemory
1026556hqminhuwuSkyscraper (JOI16_skyscraper)C++14
15 / 100
3 ms5724 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll,ll> pll; typedef pair <ll,ll> pii; typedef pair <ll,pii> piii; #define forr(_a,_b,_c) for(ll _a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(ll _a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(ll _a = (_b); _a < (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" template<class X, class Y> bool minz(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maxz(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const ll N = 5e5 + 5; const ll oo = (ll) 1e16; const ll mod = 1e9 + 7; // 998244353; ll n, l, a[N], dp[105][105][1005][4]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef hqm freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> n >> l; forr (i, 1, n){ cin >> a[i]; } sort(a + 1, a + 1 + n); dp[1][0][0][0] = 1; ll res = 0; forr (i, 1, n){ forr (j, 0, n){ forr (k, 0, l){ forr (t, 0, 2){ //if (j == 0 && t != 0) continue; if (dp[i][j][k][t]){ // cout << i << " " << j << " " << k << " " << t << " " << dp[i][j][k][t] << "\n"; } ll nk; nk = min(l + 1, k + ((j + 1) * 2 - t) * (a[i + 1] - a[i])); (dp[i + 1][j + 1][nk][t] += dp[i][j][k][t] * (j + 1 - t)) %= mod; nk = min(l + 1, k + ((j + 1) * 2 - (t + 1)) * (a[i + 1] - a[i])); (dp[i + 1][j + 1][nk][t + 1] += dp[i][j][k][t] * (2 - t)) %= mod; if (j >= 1){ nk = min(l + 1, k + (j * 2 - t) * (a[i + 1] - a[i])); (dp[i + 1][j][nk][t] += dp[i][j][k][t] * (2 * j - t)) %= mod; nk = min(l + 1, k + (j * 2 - (t + 1)) * (a[i + 1] - a[i])); (dp[i + 1][j][nk][t + 1] += dp[i][j][k][t] * (2 - t)) %= mod; } if (j - t >= 2){ nk = min (l + 1, k + ((j - 1) * 2 - t) * (a[i + 1] - a[i])); (dp[i + 1][j - 1][nk][t] += dp[i][j][k][t] * (j - t - 1)) %= mod; } if (t && j > t){ nk = min(l + 1, k + ((j - 1) * 2 - t) * (a[i + 1] - a[i])); (dp[i + 1][j - 1][nk][t] += dp[i][j][k][t] * t) %= mod; } if (t == 2 && j == 2 && i == n){ (res += dp[i][j][k][t]) %= mod; } if (t == 1 && j == 1 && i == n){ (res += dp[i][j][k][t]) %= mod; } } } } } cout << res % mod; return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...