#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
ll add(ll x,ll y){
x+=y;
if(x<0){
x%=mod;
x+=mod;
}else{
if(x>=mod) x%=mod;
}
return x;
}
ll mul(ll a,ll b){
ll ans = (a*b)%mod;
if(ans<0) ans+=mod;
return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
return uniform_int_distribution<ll>(l,r)(rng);
}
#define maxn 105
ll n,L;
ll a[maxn];
map<ll,ll> dp[maxn][maxn][2][2];
int main(){
daj_mi_malo_vremena
cin >> n >> L;
for(ll i = 1;i<=n;i++) cin >> a[i];
if(n==1){cout<<1<<endl;return 0;}
sort(a+1,a+n+1);
dp[1][1][1][0][-a[1]] = 1;
dp[1][1][0][1][-a[1]] = 1;
dp[1][1][0][0][-2*a[1]] = 1;
for(ll i = 2;i<=n;i++){
for(ll j = 1;j<=i;j++){
for(ll l = 0;l<=1;l++){
for(ll r = 0;r<=1;r++){
for(pll p : dp[i-1][j][l][r]){
ll k = p.fi;
ll cnt = p.sc;
if(k>L||k + (2*j+1-l-r)*a[i]>L) break;
dp[i][j][l][r][k] = add(dp[i][j][l][r][k],mul(cnt,2*j-l-r));
if(!l) dp[i][j][1][r][k+a[i]] = add(dp[i][j][1][r][k+a[i]],cnt);
if(!r) dp[i][j][l][1][k+a[i]] = add(dp[i][j][l][1][k+a[i]],cnt);
dp[i][j+1][l][r][k-2*a[i]] = add(dp[i][j+1][l][r][k-2*a[i]],mul(cnt,j+1-l-r));
if(!l) dp[i][j+1][1][r][k-a[i]] = add(dp[i][j+1][1][r][k-a[i]],cnt);
if(!r) dp[i][j+1][l][1][k-a[i]] = add(dp[i][j+1][l][1][k-a[i]],cnt);
dp[i][j-1][l][r][k+2*a[i]] = add(dp[i][j-1][l][r][k+2*a[i]],mul(cnt,j-1));
}
}
}
}
}
ll ans = 0;
for(pll p : dp[n][1][1][1]){
ll k = p.fi;
ll cnt = p.sc;
if(k<=L) ans = add(ans,cnt);
}
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2388 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2388 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2388 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2388 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
