#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define gcd __gcd
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
struct piii {
int first , second , third;
};
const ll MAX_N = 1 << 14 , md = 1e9 + 7;
ll tav(ll n , ll k){
ll res = 1;
while(k > 0){
if(k & 1){
res *= n;
}
n *= n;
k /= 2;
}
return res;
}
ll cnt[MAX_N][101][15];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n , l;
ll ans = 0;
cin>>n>>l;
vector<ll> a(n);
if(n <= 8){
for(int i = 0 ; i < n ; i++){
cin>>a[i];
}
int sum = 0;
sort(a.begin() , a.end());
for(int i = 1 ; i < n ; i++){
sum += abs(a[i] - a[i - 1]);
}
ans += (sum <= l);
while(next_permutation(a.begin() , a.end())){
sum = 0;
for(int i = 1 ; i < n ; i++){
sum += abs(a[i] - a[i - 1]);
}
ans += (sum <= l);
}
cout<<ans<<'\n';
return 0;
}
if(n > 14 || l > 100) return 0;
for(int i = 0 ; i < n ; i++){
cin>>a[i];
}
int h = 1 << n;
for(int i = 0 ; i < h ; i++){
for(int j = 0 ; j < n ; j++){
cnt[i][0][j] = (__builtin_popcount(i) < 2);
for(int q = 1 ; q < 101 ; q++){
cnt[i][q][j] = 0;
}
}
}
for(int i = 0 ; i < h ; i++){
if(__builtin_popcount(i) < 2) continue;
int o = 1;
for(int j = 0 ; j < n ; j++){
if(i & o){
int p = i ^ o , k = 1;
for(int q = 0 ; q < n ; q++){
if(k & p){
for(int y = 0 ; y < 101 ; y++){
int d = y + abs(a[j] - a[q]);
if(d > l) break;
cnt[i][d][j] += cnt[p][y][q];
}
}
k *= 2;
}
}
o *= 2;
}
}
for(int i = 0 ; i <= l ; i++){
for(int j = 0 ; j < n ; j++){
ans += cnt[h - 1][i][j];
}
}
cout<<ans % md<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
48876 KB |
Output is correct |
2 |
Correct |
259 ms |
194668 KB |
Output is correct |
3 |
Correct |
197 ms |
194796 KB |
Output is correct |
4 |
Correct |
258 ms |
194796 KB |
Output is correct |
5 |
Correct |
249 ms |
194668 KB |
Output is correct |
6 |
Correct |
273 ms |
194796 KB |
Output is correct |
7 |
Correct |
163 ms |
194668 KB |
Output is correct |
8 |
Correct |
191 ms |
194668 KB |
Output is correct |
9 |
Correct |
264 ms |
194668 KB |
Output is correct |
10 |
Correct |
250 ms |
194668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
58 ms |
48876 KB |
Output is correct |
12 |
Correct |
259 ms |
194668 KB |
Output is correct |
13 |
Correct |
197 ms |
194796 KB |
Output is correct |
14 |
Correct |
258 ms |
194796 KB |
Output is correct |
15 |
Correct |
249 ms |
194668 KB |
Output is correct |
16 |
Correct |
273 ms |
194796 KB |
Output is correct |
17 |
Correct |
163 ms |
194668 KB |
Output is correct |
18 |
Correct |
191 ms |
194668 KB |
Output is correct |
19 |
Correct |
264 ms |
194668 KB |
Output is correct |
20 |
Correct |
250 ms |
194668 KB |
Output is correct |
21 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |