Submission #1261850

#TimeUsernameProblemLanguageResultExecution timeMemory
1261850arashmemarSkyscraper (JOI16_skyscraper)C++20
0 / 100
2092 ms324 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 101, maxl = 1001, mod = 1e9 + 7; int dp[maxn][maxn][3][3][maxl], a[maxn]; int main() { int n, l; cin >> n >> l; for (int i = 1;i <= n;i++) { cin >> a[i]; } sort(a + 1, a + 1 + n); do { int ret = 0; for (int i = 1;i < n;i++) { ret += abs(a[i] - a[i + 1]); } if (ret == 5) { for (int i = 1;i <= n;i++) { cout << a[i] << ' '; } cout << endl; } }while (next_permutation(a + 1, a + n + 1)); sort(a + 1, a + 1 + n); dp[0][0][0][0][0] = 1; for (int i = 0;i <= n;i++) { for (int j = 0;j <= n;j++) { for (int noe = 0;noe < 2;noe++) { for (int nos = 0;nos < 2;nos++) { for (int c = 0;c <= l;c++) { long long int p = dp[i][j][nos][noe][c]; if (p) { // cout << i << ' ' << j << ' ' << nos << ' ' << noe << ' ' << c << " : " << p << endl; } int cc = c + (2 * j - nos - noe) * (a[i + 1] - a[i]); if (p == 0 or cc > l or i == n) { continue; } dp[i + 1][j][nos][noe][cc] += p * (j - noe) % mod; dp[i + 1][j][nos][noe][cc] %= mod; dp[i + 1][j][nos][noe][cc] += p * (j - nos) % mod; dp[i + 1][j][nos][noe][cc] %= mod; dp[i + 1][j + 1][nos][noe][cc] += p; dp[i + 1][j + 1][nos][noe][cc] %= mod; if (j > 1) { dp[i + 1][j - 1][nos][noe][cc] += p * ((j - noe - nos) * (j - nos - 1) + nos * (j - nos - noe)) % mod; if (i == n - 1) { dp[i + 1][j - 1][nos][noe][cc] += p * nos * noe; } dp[i + 1][j - 1][nos][noe][cc] %= mod; } if (nos == 0) { dp[i + 1][j + 1][nos + 1][noe][cc] += p; dp[i + 1][j + 1][nos + 1][noe][cc] %= mod; dp[i + 1][j][nos + 1][noe][cc] += p * (j - noe) % mod; if (i == n - 1) { dp[i + 1][j][nos + 1][noe][cc] += p * noe; } dp[i + 1][j][nos + 1][noe][cc] %= mod; } if (noe == 0) { dp[i + 1][j][nos][noe + 1][cc] += p * (j - nos) % mod; if (i == n - 1) { dp[i + 1][j][nos][noe + 1][cc] += p * nos; } dp[i + 1][j][nos][noe + 1][cc] %= mod; dp[i + 1][j + 1][nos][noe + 1][cc] += p; dp[i + 1][j + 1][nos][noe + 1][cc] %= mod; } } } } } } long long int ans = 0; for (int i = 0;i <= l;i++) { ans += dp[n][1][1][1][i]; ans %= mod; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...