#include <iostream>
#include <chrono>
#include <algorithm>
#include <cstring>
#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;
}
int dp[(1 << 15)][15][500];
int val[maxn];
///maxdiff!!!
int n , max_sum;
void read()
{
cin >> n >> max_sum;
for(int i = 1; i <= n; i++) cin >> val[i];
sort(val + 1 , val + 1 + n);
val[0] = val[1];
}
int ans = 0;
void subtask1()
{
sort(val + 1 , val + 1 + n);
int cur_sum = 0;
do
{
cur_sum = 0;
for(int 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(int mask = 0; mask < (1 << n) - 1; mask++)
{
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= max_sum; j++)
{
if(dp[mask][i][j])
{
for(int k = 1; k <= n; k++)
{
if(!(mask & (1 << (k - 1))))
{
int new_mask = (mask | (1 << (k - 1)));
int 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(int i = 1; i <= n; i++)
for(int j = 0; j <= max_sum; j++)
ans = (ans + dp[(1 << n) - 1][i][j]) % mod;
cout << ans << endl;
}
int dp2[maxn][maxn][maxdiff][2][2];
int subtask3(int sum , int l , int r , int i , int j)
{
int new_sum = sum + (j * 2 + l + r) * (val[i] - val[i - 1]);
if(new_sum > max_sum) return 0;
if(i == n) return j == 0? 1 : 0;
if(dp2[i][j][sum][l][r] != -1) return dp2[i][j][sum][l][r];
int 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:19:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
19 | #pragma GCC target(avx2)
| ^~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:166:9: error: 'assert' was not declared in this scope
166 | assert(false);
| ^~~~~~
skyscraper.cpp:5:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
4 | #include <cstring>
+++ |+#include <cassert>
5 |
