#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define double long double
const int mod=1e9+7,mxn=1e5+5,lg=60,inf=1e9,minf=-1e18,Mxn=1e6+50000;
int dp[102][102][1002][4];
int32_t main(){
fastio
//dp[i][num of com][cur sum][border have]
int base=1e3;
int n,l;cin>>n>>l;
vector<int>v(n);
for(int i=0;i<n;i++)cin>>v[i];
sort(all(v));
v.pb(inf);
if(2*(v[1]-v[0]))dp[1][1][2*(v[1]-v[0])][0]=1;
if(v[1]-v[0]<=l)dp[1][1][v[1]-v[0]][1]=2;
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
for(int sum=0;sum<=l;sum++){
for(int k=0;k<3;k++){
int nsum=0;
if(dp[i][j][sum][k]==0)continue;
//cout<<dp[i][j][sum][k]<<" "<<i<<" "<<j<<" "<<sum<<" "<<k<<" "<<"G\n";
//create
nsum=(sum+((v[i+1]-v[i])*((j+1)*2-k)));
if(nsum<=l&&nsum>=0){
dp[i+1][j+1][nsum][k]=(dp[i+1][j+1][nsum][k]+(dp[i][j][sum][k]*(j+1-k))%mod)%mod;
}
//merge
nsum=(sum+((v[i+1]-v[i])*((j-1)*2-k)));
if(nsum<=l&&nsum>=0)dp[i+1][j-1][nsum][k]=(dp[i+1][j-1][nsum][k]+(dp[i][j][sum][k]*(j-1))%mod)%mod;
//fill border
//fill border by creating new one
nsum=(sum+((v[i+1]-v[i])*(((j+1)*2)-k-1)));
if(nsum<=l&&nsum>=0){
dp[i+1][j+1][nsum][k+1]=(dp[i+1][j+1][nsum][k+1]+(dp[i][j][sum][k]*(2-k))%mod)%mod;
}
/*
missing case where
a>b<c
*/
//fill border by attaching to the existing one
nsum=(sum+(v[i+1]-v[i])*((j*2)-k-1));
if(nsum<=l&&nsum>=0){
//cout<<"B\n";
dp[i+1][j][nsum][k+1]=(dp[i+1][j][nsum][k+1]+(dp[i][j][sum][k]*(2-k))%mod)%mod;
}
//attach
nsum=(sum+(v[i+1]-v[i])*((j*2)-k));
if(nsum<=l&&nsum>=0)dp[i+1][j][nsum][k]=(dp[i+1][j][nsum][k]+(dp[i][j][sum][k]*((j-k)*2+k))%mod)%mod;//stick it
}
}
}
}//2 3 6 6
//2 3 3 3
int ans=0;
for(int i=0;i<=l;i++){
//cout<<dp[n][1][i][2]<<" "<<i<<'\n';
ans=(ans+dp[n][1][i][2])%mod;
}
cout<<ans;
/*
*/
return 0;
}
/*
*/
Compilation message
skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:50:6: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
50 | if(2*(v[1]-v[0]))dp[1][1][2*(v[1]-v[0])][0]=1;
| ~^~~~~~~~~~~~
skyscraper.cpp:44:6: warning: unused variable 'base' [-Wunused-variable]
44 | int base=1e3;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2904 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
