#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
void solve(){
ll n,m;
cin>>n>>m;
vector<ll> v(n);
for(auto &i:v) cin>>i;
vector<ll> v1;
for(int mask=0;mask<(1<<n/2);mask++){
ll sum = 0;
for(int i=0;i<(n>>1);i++){
if((1<<i)&mask){
sum += v[i];
}
}
v1.push_back(sum);
}
sort(v1.begin(),v1.end());
int rem = n-(n>>1);
ll ans = 0;
vector<ll> v2;
for(int mask=0;mask<(1<<rem);mask++){
ll sum = 0;
for(int i=0;i<rem;i++){
if((1<<i)&mask){
sum += v[(n>>1)+i];
}
}
v2.push_back(sum);
}
sort(v2.begin(),v2.end());
for(auto i : v1){
int upper = upper_bound(v2.begin(),v2.end(),m-i) - v2.begin();
ans += upper;
}
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
1920 KB |
Output is correct |
2 |
Correct |
80 ms |
5332 KB |
Output is correct |
3 |
Correct |
370 ms |
20952 KB |
Output is correct |
4 |
Correct |
77 ms |
5432 KB |
Output is correct |
5 |
Correct |
13 ms |
1492 KB |
Output is correct |
6 |
Correct |
10 ms |
964 KB |
Output is correct |
7 |
Correct |
16 ms |
1488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
2868 KB |
Output is correct |
2 |
Correct |
28 ms |
2016 KB |
Output is correct |
3 |
Correct |
131 ms |
10568 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
6 ms |
984 KB |
Output is correct |
6 |
Correct |
17 ms |
1600 KB |
Output is correct |
7 |
Correct |
17 ms |
1624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
3540 KB |
Output is correct |
2 |
Correct |
119 ms |
6612 KB |
Output is correct |
3 |
Correct |
127 ms |
6600 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
86 ms |
6616 KB |
Output is correct |
6 |
Correct |
295 ms |
20824 KB |
Output is correct |
7 |
Correct |
107 ms |
6608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
240 ms |
12712 KB |
Output is correct |
2 |
Correct |
27 ms |
1932 KB |
Output is correct |
3 |
Correct |
9 ms |
968 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
8 ms |
856 KB |
Output is correct |
6 |
Correct |
228 ms |
12756 KB |
Output is correct |
7 |
Correct |
16 ms |
1532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2012 KB |
Output is correct |
2 |
Correct |
78 ms |
5332 KB |
Output is correct |
3 |
Correct |
9 ms |
984 KB |
Output is correct |
4 |
Correct |
9 ms |
984 KB |
Output is correct |
5 |
Correct |
87 ms |
6520 KB |
Output is correct |
6 |
Correct |
25 ms |
2008 KB |
Output is correct |
7 |
Correct |
300 ms |
20796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
319 ms |
20776 KB |
Output is correct |
2 |
Correct |
29 ms |
2008 KB |
Output is correct |
3 |
Correct |
10 ms |
984 KB |
Output is correct |
4 |
Correct |
349 ms |
20824 KB |
Output is correct |
5 |
Correct |
107 ms |
10460 KB |
Output is correct |
6 |
Correct |
17 ms |
1488 KB |
Output is correct |
7 |
Correct |
34 ms |
2896 KB |
Output is correct |