#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
const ll mod=1000000007;
ll solve(ll n,ll L,vi v){
vvvi dp(3,vvi(n+1,vi(L+1)));
dp[0][1][0]=1;dp[1][1][0]=2;dp[2][1][0]=1;
REP(i,1,n){
vvvi ndp(3,vvi(n+1,vi(L+1)));
rep(j,3)REP(k,1,n+1)rep(l,L+1)if(dp[j][k][l]&&l+(k*2-j)*(v[i]-v[i-1])<=L&&k*2-j>0)ndp[j][k][l+(k*2-j)*(v[i]-v[i-1])]+=dp[j][k][l];
rep(j,3)REP(k,1,n+1)rep(l,L+1)dp[j][k][l]=ndp[j][k][l]%mod;
rep(j,3)REP(k,1,n+1)rep(l,L+1)ndp[j][k][l]=0;
rep(j,3)REP(k,1,n+1)rep(l,L+1)if(dp[j][k][l]){
if(k>1)ndp[j][k-1][l]+=dp[j][k][l]*(k-1)%mod;
if(j<2)ndp[j+1][k][l]+=dp[j][k][l]*(2-j)%mod;
ndp[j][k][l]+=dp[j][k][l]*(2*k-j)%mod;
ndp[j][k+1][l]+=dp[j][k][l]*(k+1-j)%mod;
if(j<2)ndp[j+1][k+1][l]+=dp[j][k][l]*(2-j)%mod;
}
rep(j,3)REP(k,1,n+1)rep(l,L+1){
dp[j][k][l]=ndp[j][k][l]%mod;
// if(dp[j][k][l])cout<<j<<' '<<k<<' '<<l<<' '<<dp[j][k][l]<<endl;
}
}
ll ans=0;
rep(i,L+1)ans+=dp[2][1][i];
return ans%mod;
}
int main(){
ll n,L;cin>>n>>L;
vi v(n);
rep(i,n)cin>>v[i];
sort(all(v));
out(solve(n,L,v));
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
688 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
724 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Correct |
1 ms |
304 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
688 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
724 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
300 KB |
Output is correct |
| 15 |
Correct |
1 ms |
304 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
2 ms |
340 KB |
Output is correct |
| 22 |
Correct |
133 ms |
3996 KB |
Output is correct |
| 23 |
Correct |
214 ms |
5804 KB |
Output is correct |
| 24 |
Correct |
179 ms |
4496 KB |
Output is correct |
| 25 |
Correct |
226 ms |
5972 KB |
Output is correct |
| 26 |
Correct |
193 ms |
5056 KB |
Output is correct |
| 27 |
Correct |
56 ms |
1684 KB |
Output is correct |
| 28 |
Correct |
70 ms |
1988 KB |
Output is correct |
| 29 |
Correct |
146 ms |
3840 KB |
Output is correct |
| 30 |
Correct |
230 ms |
5916 KB |
Output is correct |
