#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
const ll mod = 1'000'000'007LL;
ll ad(ll a, ll b)
{
return (a+b) % mod;
}
ll mul(ll a, ll b)
{
return (a*b) % mod;
}
void selfadd(int& a, int b)
{
a = ad(a, b);
}
int N, L;
int validlen(int x)
{
return 0 <= x && x <= L;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> L;
vi A(1+N, 0);
for(int i = 1; i <= N; i++)
cin >> A[i];
sort(A.begin(), A.end());
int DP[1+N][1+N][1+L][1+2];
for(int i = 0; i <= N; i++)
for(int j = 0; j <= N; j++)
for(int l = 0; l <= L; l++)
for(int e = 0; e <= 2; e++)
DP[i][j][l][e] = 0;
DP[1][1][0][0] = DP[1][1][0][2] = 1;
DP[1][1][0][1] = 2;
for(int i = 1; i <= N; i++)
{
// cerr << "\n\n\n";
for(int j = 1; j <= i; j++)
{
// cerr << "\n\n";
for(int l = 0; l <= L; l++)
{
// cerr << "\n";
for(int e = 0; e <= 2; e++)
{
// cerr << i << ' ' << j << ' ' << l << ' ' << e << " : " << DP[i][j][l][e] << '\n';
if(i >= N)
continue;
int nl = l + (2*j - e) * (A[i+1] - A[i]);
if(!validlen(nl))
continue;
// cerr << "proceeding\n";
//case 1: building i+1 forms new component
selfadd(DP[i+1][j+1][nl][e], mul(DP[i][j][l][e], j+1 - e));
//case 2: building i+1 is attached to the left/right of some component
// if(i == 1 && j == 1 && l == 0 && e == 0)
// cerr << DP[i][j][l][e] << ' ' << 2*j - e << " -> " << i+1 << ' ' << j << ' ' << l + (2*j - e) * (A[i+1] - A[i]) << ' ' << e << '\n';
selfadd(DP[i+1][j][nl][e], mul(DP[i][j][l][e], 2*j - e));
//case 3: building i+1 merges two components
if(j >= 2)
selfadd(DP[i+1][j-1][nl][e], mul(DP[i][j][l][e], j-1));
//case 4: building i+1 creates an endpoint
if(e < 2)
selfadd(DP[i+1][j][nl][e+1], mul(DP[i][j][l][e], 2 - e));
//case 5: building i+1 simultaneously forms a new component and creates endpoint
if(e < 2)
selfadd(DP[i+1][j+1][nl][e+1], mul(DP[i][j][l][e], 2 - e));
}
}
}
}
ll res = 0;
for(int l = 0; l <= L; l++)
res = ad(res, DP[N][1][l][2]);
assert(0 <= res && res < mod);
cout << res << '\n';
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:111:2: error: 'assert' was not declared in this scope
111 | assert(0 <= res && res < mod);
| ^~~~~~
skyscraper.cpp:4:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
3 | #include <algorithm>
+++ |+#include <cassert>
4 | using namespace std;
