This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
const int NMAX = 1e2 + 3, KMAX = 1e3 + 3;
const int MOD = 1e9 + 7;
int N, K, A[NMAX];
int New[NMAX][KMAX][2][2], Old[NMAX][KMAX][2][2];
static inline void Read ()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
for(int i = 1; i <= N; ++i)
cin >> A[i];
return;
}
static inline void Initialize ()
{
New[0][0][1][1] = New[0][0][0][1] = New[0][0][1][0] = New[0][0][0][0] = 1;
return;
}
void Add (int &x, int y, int z)
{
x = (1ll * x + 1LL * y * z) % (1ll * MOD);
return;
}
static inline void Find_Answer ()
{
int ans = 0;
for(int i = 0; i <= K; ++i)
Add(ans, 1, New[0][i][0][0]);
cout << ans << '\n';
return;
}
int main()
{
Read();
sort(A + 1, A + N + 1);
for(int i = 1; i <= N; ++i)
A[i] = A[i+1] - A[i];
Initialize();
for(int i = 1; i < N; ++i)
{
memcpy(Old, New, sizeof(New));
memset(New, 0, sizeof(New));
for(int j = 0; j <= N; ++j)
for(int k = 0; k <= K; ++k)
for(int F = 0; F < 2; ++F)
for(int S = 0; S < 2; ++S)
{
int new_k = k + A[i] * ((j << 1) + F + S);
if(new_k > K)
continue;
Add(New[j + 1][new_k][F][S], j, Old[j][k][F][S]);
Add(New[j][new_k][F][S], (j << 1), Old[j][k][F][S]);
if(j > 0)
Add(New[j - 1][new_k][F][S], j, Old[j][k][F][S]);
if(F > 0)
{
Add(New[j + 1][new_k][1][S], 1, Old[j][k][F][S]);
Add(New[j + 1][new_k][0][S], 1, Old[j][k][F][S]);
Add(New[j][new_k][1][S], 1, Old[j][k][F][S]);
Add(New[j][new_k][0][S], 1, Old[j][k][F][S]);
}
if(S > 0)
{
Add(New[j + 1][new_k][F][1], 1, Old[j][k][F][S]);
Add(New[j + 1][new_k][F][0], 1, Old[j][k][F][S]);
Add(New[j][new_k][F][1], 1, Old[j][k][F][S]);
Add(New[j][new_k][F][0], 1, Old[j][k][F][S]);
}
}
}
Find_Answer();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |