Submission #74595

#TimeUsernameProblemLanguageResultExecution timeMemory
74595nobikSkyscraper (JOI16_skyscraper)C++14
100 / 100
295 ms79392 KiB
#include <bits/stdc++.h> using namespace std; const int mod = 1000 * 1000 * 1000 + 7; const int N = 105; const int L = 1005; int n, l, a[N], f[N][L][N][2][2]; void add(int &x, int y) { x += y; if (x >= mod) { x -= mod; } } int main() { cin >> n >> l; for (int i = 0; i < n; ++i) { cin >> a[i]; } sort(a, a + n); reverse(a, a + n); for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) f[0][0][1][x][y] = 1; for (int i = 1; i < n; ++i) { for (int j = 0; j <= l; ++j) { for (int w = 1; w <= i; ++w) { for (int x = 0; x < 2; ++x) { for (int y = 0; y < 2; ++y) { int r, nj, nw, p; r = f[i - 1][j][w][x][y]; nj = j + (2 * w - x - y) * (a[i - 1] - a[i]); if (r == 0 || nj > l) { continue; } if (w == 1 && x && y) { continue; } { nw = w + 1; add(f[i][nj][nw][x][y], r); if (x == 0) add(f[i][nj][nw][1][y], r); if (y == 0) add(f[i][nj][nw][x][1], r); } { add(f[i][nj][w][x][y], 1LL * (2 * w - x - y) * r % mod); } { { nw = w - 1; p = (x ? w - x - y : 0) + (y ? w - x - y : 0) + (w - x - y) * (w - x - y - 1); if (nw == 1 && x && y) ++p; add(f[i][nj][nw][x][y], 1LL * p * r % mod); } if (x == 0) { p = w - (w > 1 && y); add(f[i][nj][w][1][y], 1LL * p * r % mod); } if (y == 0) { p = w - (w > 1 && x); add(f[i][nj][w][x][1], 1LL * p * r % mod); } } } } } } } int r = 0; for (int i = 0; i <= l; ++i) add(r, f[n - 1][i][1][1][1]); cout << r << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...