# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
118575 | IOrtroiii | Skyscraper (JOI16_skyscraper) | C++14 | 144 ms | 19468 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 1005;
const int mod = 1e9 + 7;
void add(int &x, int y) {
x += y; if (x >= mod) x -= mod;
}
int mul(int x, int y) {
return (long long) x * y % mod;
}
int a[N];
int f[N][N][M][2][2];
int main() {
int n, m;
scanf("%d %d", &n, &m);
if (n == 1) {
puts("1");
return 0;
}
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
sort(a + 1, a + 1 + n);
for (int i = n; i > 1; --i) {
a[i] -= a[i - 1];
}
a[1] = 0;
f[0][0][0][0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
for (int k = 0; k <= m; ++k) {
for (int l = 0; l < 2; ++l) {
for (int r = 0; r < 2; ++r) {
int ways = f[i][j][k][l][r];
if (!ways) continue;
int nk = k + a[i + 1] * (2 * j - l - r);
if (nk > m) continue;
// fix left
if (!l) {
int coef = j - r;
if (i == n - 1) coef += r;
add(f[i + 1][j][nk][1][r], mul(coef, ways));
add(f[i + 1][j + 1][nk][1][r], ways);
}
// fix right
if (!r) {
int coef = j - l;
if (i == n - 1) coef += l;
add(f[i + 1][j][nk][l][1], mul(coef, ways));
add(f[i + 1][j + 1][nk][l][1], ways);
}
// merge one (not fix)
add(f[i + 1][j][nk][l][r], mul(2 * j - l - r, ways));
// make new (now fix)
add(f[i + 1][j + 1][nk][l][r], ways);
// merge two
if (j > 1) {
int coef = (j - l - r) * (j - 1);
// left
if (i == n - 1) {
coef += (l && r);
}
add(f[i + 1][j - 1][nk][l][r], mul(coef, ways));
}
}
}
}
}
}
int ans = 0;
for (int i = 0; i <= m; ++i) {
add(ans, f[n][1][i][1][1]);
}
printf("%d\n", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |