Submission #380986

#TimeUsernameProblemLanguageResultExecution timeMemory
380986pure_memSkyscraper (JOI16_skyscraper)C++14
100 / 100
123 ms50924 KiB
#include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int N = 103; const int mod = 1e9 + 7; int n, d, a[N]; ll dp[N][N][1001][3]; int main () { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> d; for(int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1); if(n == 1) return cout << 1, 0; a[n + 1] = 10000; dp[0][0][0][0] = 1; for(int i = 1;i <= n;i++){ for(int j = 1;j <= i;j++){ for(int k = 0;k <= d;k++){ for(int m = 0;m < 3;m++){ int cost = (2 * j - m) * (a[i + 1] - a[i]); if(cost > k || i + j + 1 - m > n) continue; dp[i][j][k][m] += dp[i - 1][j - 1][k - cost][m]; if(m) dp[i][j][k][m] += (3 - m) * dp[i - 1][j - 1][k - cost][m - 1]; dp[i][j][k][m] += (2 * j - m) * dp[i - 1][j][k - cost][m]; if(m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - cost][m - 1]; if(m == 2){ if(i == n) dp[i][j][k][m] += dp[i - 1][j][k - cost][m - 1]; else if(j > 1) dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - cost][m - 1]; } if(m == 2){ if(i == n) dp[i][j][k][m] += dp[i - 1][j + 1][k - cost][m]; else dp[i][j][k][m] += j * (j - 1) * dp[i - 1][j + 1][k - cost][m]; } else if(m == 1) dp[i][j][k][m] += j * j * dp[i - 1][j + 1][k - cost][m]; else dp[i][j][k][m] += j * (j + 1) * dp[i - 1][j + 1][k - cost][m]; dp[i][j][k][m] %= mod; } } } } ll ans = 0; for(int i = 0;i <= d;i++) ans += dp[n][1][i][2]; cout << ans % mod; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...