Submission #1261418

#TimeUsernameProblemLanguageResultExecution timeMemory
1261418Bui_Quoc_CuongSkyscraper (JOI16_skyscraper)C++20
15 / 100
1 ms840 KiB
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; #define int long long void add(int &x, const int y){ x+= y; if (x >= MOD) x-= MOD; } int n, L; int a[1006]; int dp[105][105][1005][3]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> L; for(int i = 1; i <= n; i++){ cin >> a[i]; } sort(a + 1, a + 1 + n); dp[0][0][0][0] = 1; for(int i = 0; i <= n - 1; i++) for(int j = 0; j <= n; j++) for(int s = 0; s <= L; s++){ for(int e = 0; e <= 2; e++) if(dp[i][j][s][e] > 0){ int g = (2 * j - e) * (a[i + 1] - a[i]); if (s + g > L) continue; /// tao 1 tplt moi va khong chua ket thuc add(dp[i + 1][j + 1][s + g][e], dp[i][j][s][e]); /// tao 1 tplt moi va ket thuc add(dp[i + 1][j + 1][s + g][e + 1], 1LL * dp[i][j][s][e] * (2 - e) % MOD); /// chen a[i] vao 1 tplt va ko ket thuc add(dp[i + 1][j][s + g][e], 1LL * (2 * j - e) * dp[i][j][s][e] % MOD); /// chen a[i] vao 1 tplt va ket thuc if(e == 0){ add(dp[i + 1][j][s + g][1], 1LL * 2 * j % MOD * dp[i][j][s][e] % MOD); } if(e == 1){ if(j == 1 && i + 1 == n){ add(dp[i + 1][j][s + g][2], dp[i][j][s][e]); } else{ add(dp[i + 1][j][s + g][2], 1LL * dp[i][j][s][e] * (j - 1) % MOD); } } /// dung a[i] noi 2 tplt if(j >= 2){ if(e == 0){ add(dp[i + 1][j - 1][s + g][0], 1LL * dp[i][j][s][e] * j % MOD * (j - 1) % MOD); } if(e == 1){ add(dp[i + 1][j - 1][s + g][1], 1LL * dp[i][j][s][e] * (j - 1) % MOD * (j - 1) % MOD); } } if(e == 2){ if(j == 2 && i + 1 == n){ add(dp[i + 1][j - 1][s + g][2], dp[i][j][s][e]); } else if(j >= 3){ add(dp[i + 1][j - 1][s + g][2], 1LL * dp[i][j][s][e] * (j - 2) % MOD * (j - 1) % MOD); } } } } int ans = 0; for(int i = 0; i <= L; i++) add(ans, dp[n][1][i][2]); cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...