#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &v, T val) { return v < val ? (v = val, true) : false; }
template<class T>
bool chmin(T &v, T val) { return val < v ? (v = val, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_L = 1005, p = 1e9+7, MAX_N = 105, MAX_K = 3;
int n, L, a[MAX_N], cnt[MAX_N];
int dp[3][3][MAX_N][MAX_N][MAX_L], tmp[3][3][MAX_N][MAX_N][MAX_L];
void add(int &v, int val) { v = (v + val) % p; return; v += val - p, v += (v>>31) & p; }
void add(ll &v, int val) { v = (v + val) % p; return; v += val - p, v += (v>>63) & p; }
ll C(ll a, ll b) { assert(b == 2); return (a * (a-1) / 2); }
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> L;
for (int i = 1;i <= n;++i) {
cin >> a[i];
}
sort(a+1, a+n+1);
auto dp = ::dp;
auto tmp = ::tmp;
// dp[d][a][b][c][cost]
dp[0][0][0][0][0] = 2;
for (int i = 0;i <= n;++i) {
int gap = a[i+1] - a[i];
DE(i, gap);
for (int d = 0;d <= 2;++d)
for (int a = 0;a <= 2;++a)
for (int b = 0;b <= i;++b) for (int c = 0;c + a + b <= i;++c) {
for (int cost = 0;cost <= L;++cost) if (dp[d][a][b][c][cost]) {
ll now = dp[d][a][b][c][cost];
dp[d][a][b][c][cost] = 0;
ll nc = cost + (a + (b + c) * 2) * gap;
DE(d,a,b,c,cost,now);
if (i == n) {
tmp[d][a][b][c][cost] = now;
continue;
}
if (nc > L) continue;
// if deg == 1
if (d < 2) {
// if point back
// to c
if (c)
add(tmp[d + 1][a + 1][b][c - 1][nc], now * 2 * c % p);
// to b
if (b)
add(tmp[d + 1][a + 1][b - 1][c][nc], now * b % p);
// to a
if (a && b == 0 && c == 0)
add(tmp[d + 1][a - 1][b][c][nc], now * a % p);
// if point forward
add(tmp[d + 1][a + 1][b][c][nc], now);
}
// if deg == 2
if (a && b)
add(tmp[d][a][b - 1][c][nc], now * a * b % p);
if (a && c)
add(tmp[d][a][b][c - 1][nc], now * a * c * 2 % p);
if (b && c)
add(tmp[d][a][b - 1][c][nc], now * b * c * 2 % p);
// self to aa, bb, cc
if (a >= 2)
add(tmp[d][a - 2][b][c][nc], now);
if (b >= 2)
add(tmp[d][a][b - 2][c + 1][nc], now * C(b, 2) % p);
if (c >= 2)
add(tmp[d][a][b][c - 1][nc], now * C(c, 2) * 4 % p);
// self be b
add(tmp[d][a][b + 1][c][nc], now);
// self to a, b, c
if (a)
add(tmp[d][a][b][c][nc], now * a % p);
if (b)
add(tmp[d][a][b - 1][c + 1][nc], now * b % p);
if (c)
add(tmp[d][a][b][c][nc], now * c * 2 % p);
}
}
swap(dp, tmp);
}
cout << accumulate(dp[2][0][0][0], dp[2][0][0][0] + L + 1, 0ll) % p << '\n';
}
Compilation message
skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:19:17: warning: statement has no effect [-Wunused-value]
19 | #define DE(...) 0
| ^
skyscraper.cpp:43:3: note: in expansion of macro 'DE'
43 | DE(i, gap);
| ^~
skyscraper.cpp:19:17: warning: statement has no effect [-Wunused-value]
19 | #define DE(...) 0
| ^
skyscraper.cpp:51:7: note: in expansion of macro 'DE'
51 | DE(d,a,b,c,cost,now);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1132 KB |
Output is correct |
| 4 |
Correct |
3 ms |
876 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1004 KB |
Output is correct |
| 7 |
Correct |
2 ms |
876 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1132 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1388 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
