#include <iostream>
#include <chrono>
#include <algorithm>
#include <cstring>
#include <cassert>
#define maxn 105
#define maxdiff 505
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define mod 1000000007
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "fast-math" , "unroll-loops")
#pragma GCC target(avx2)
using namespace std;
std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}
long long dp[(1 << 15)][15][500];
long long val[maxn];
///maxdiff!!!
long long n , max_sum;
void read()
{
cin >> n >> max_sum;
for(long long i = 1; i <= n; i++) cin >> val[i];
sort(val + 1 , val + 1 + n);
val[0] = val[1];
}
long long ans = 0;
void subtask1()
{
sort(val + 1 , val + 1 + n);
long long cur_sum = 0;
do
{
cur_sum = 0;
for(long long i = 2; i <= n; i++) cur_sum += abs(val[i - 1] - val[i]);
if(cur_sum <= max_sum) ans++;
}while(next_permutation(val + 1 , val + 1 + n));
cout << ans << endl;
}
void subtask2()
{
dp[0][0][0] = 1;
for(long long mask = 0; mask < (1 << n) - 1; mask++)
{
for(long long i = 0; i <= n; i++)
{
for(long long j = 0; j <= max_sum; j++)
{
if(dp[mask][i][j])
{
for(long long k = 1; k <= n; k++)
{
if(!(mask & (1 << (k - 1))))
{
long long new_mask = (mask | (1 << (k - 1)));
long long pom;
if(mask == 0) pom = 0;
else pom = j + abs(val[i] - val[k]);
dp[new_mask][k][pom] = (dp[new_mask][k][pom] + dp[mask][i][j]) % mod;
}
}
}
}
}
}
for(long long i = 1; i <= n; i++)
for(long long j = 0; j <= max_sum; j++)
ans = (ans + dp[(1 << n) - 1][i][j]) % mod;
cout << ans << endl;
}
long long dp2[maxn][maxn][maxdiff][2][2];
long long subtask3(long long sum , long long l , long long r , long long i , long long j)
{
long long new_sum = sum + (j * 2 + l + r) * (val[i] - val[i - 1]);
if(new_sum > max_sum) return 0;
if(j < 0) return 0;
if(i == n) return j == 0;
long long &cur_ans = dp2[i][j][sum][l][r];
if(cur_ans != -1) return cur_ans;
cur_ans = 0;
cur_ans += subtask3(new_sum , l , 1 , i + 1, j); ///dqsno
cur_ans += subtask3(new_sum , l , 1 , i + 1 , j - 1);
cur_ans += subtask3(new_sum , 1 , r , i + 1 , j); ///lqvo
cur_ans += subtask3(new_sum , 1 , r , i + 1 , j - 1);
cur_ans += subtask3(new_sum , l , r , i + 1 , j) * 2 * j; /// dobavi
cur_ans += subtask3(new_sum , l , r , i + 1 , j + 1); ///novo
cur_ans += subtask3(new_sum , l , r , i + 1 , j - 1) * (j - 1) * j; ///mergeni
cur_ans %= mod;
return (cur_ans % mod);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
startT = std::chrono::high_resolution_clock::now();
///control
read();
///
if(n <= 8) subtask1();
else if(n <= 14) subtask2();
else
{
memset(dp2 , -1 , sizeof(dp2));
///assert(false);
cout << subtask3(0 , 0 , 0 , 1 , 0) << endl;
}
return 0;
}
Compilation message
skyscraper.cpp:20:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
20 | #pragma GCC target(avx2)
| ^~~~
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
