//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
// #include <bits/extc++.h>
using namespace std;
#define debug(s) cout << #s << " = " << s << endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a, val) memset(a, val, sizeof (a))
#define PB push_back
#define endl '\n'
typedef long long ll;
inline int myrand(int l, int r) {
int ret = rand(); ret <<= 15; ret ^= rand();
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
return os<<"(" <<p.first<<", "<<p.second<<")"; }
typedef pair<int, int> ii;
template<typename T> using min_pq =
std::priority_queue<T, vector<T>, greater<T> >;
//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};
void gen(vector<ll> &vec, int pos, ll sum, vector<ll> &to) {
if(pos == vec.size()) return void(to.emplace_back(sum));
gen(vec, pos + 1, sum + vec[pos], to);
gen(vec, pos + 1, sum, to);
}
int32_t main () {
// freopen("in", "r", stdin);
ll B; int n; cin >> n >> B;
vector<ll> v(n);
for(ll &b : v) cin >> b;
if(n == 1) {
cout << 1 + int(v[0] <= B) << endl;
return 0;
}
vector<ll> Left(v.begin(), v.begin() + (n >> 1) + 1), Right(v.begin() + (n >> 1) + 1, v.end());
vector<ll> L, R;
gen(Left, 0, 0, L);
gen(Right, 0, 0, R);
sort(all(R));
ll ans = 0;
for(ll b : L) {
ans += upper_bound(all(R), B - b) - R.begin();
}
cout << ans << endl;
}
Compilation message
bobek.cpp: In function 'int myrand(int, int)':
bobek.cpp:18:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
^~
bobek.cpp:18:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
^~~
bobek.cpp: In function 'void gen(std::vector<long long int>&, int, ll, std::vector<long long int>&)':
bobek.cpp:35:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pos == vec.size()) return void(to.emplace_back(sum));
~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
356 KB |
Output is correct |
2 |
Correct |
2 ms |
432 KB |
Output is correct |
3 |
Correct |
3 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
544 KB |
Output is correct |
2 |
Correct |
2 ms |
592 KB |
Output is correct |
3 |
Correct |
2 ms |
616 KB |
Output is correct |
4 |
Correct |
3 ms |
616 KB |
Output is correct |
5 |
Correct |
2 ms |
616 KB |
Output is correct |
6 |
Correct |
3 ms |
628 KB |
Output is correct |
7 |
Correct |
2 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
640 KB |
Output is correct |
2 |
Correct |
3 ms |
660 KB |
Output is correct |
3 |
Correct |
3 ms |
676 KB |
Output is correct |
4 |
Correct |
3 ms |
680 KB |
Output is correct |
5 |
Correct |
4 ms |
688 KB |
Output is correct |
6 |
Correct |
3 ms |
688 KB |
Output is correct |
7 |
Correct |
3 ms |
692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
2768 KB |
Output is correct |
2 |
Correct |
141 ms |
6848 KB |
Output is correct |
3 |
Correct |
717 ms |
25244 KB |
Output is correct |
4 |
Correct |
132 ms |
25244 KB |
Output is correct |
5 |
Correct |
16 ms |
25244 KB |
Output is correct |
6 |
Correct |
6 ms |
25244 KB |
Output is correct |
7 |
Correct |
14 ms |
25244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
25244 KB |
Output is correct |
2 |
Correct |
36 ms |
25244 KB |
Output is correct |
3 |
Correct |
280 ms |
25244 KB |
Output is correct |
4 |
Correct |
2 ms |
25244 KB |
Output is correct |
5 |
Correct |
8 ms |
25244 KB |
Output is correct |
6 |
Correct |
13 ms |
25244 KB |
Output is correct |
7 |
Correct |
13 ms |
25244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
25244 KB |
Output is correct |
2 |
Correct |
169 ms |
25244 KB |
Output is correct |
3 |
Correct |
174 ms |
25244 KB |
Output is correct |
4 |
Correct |
4 ms |
25244 KB |
Output is correct |
5 |
Correct |
52 ms |
25244 KB |
Output is correct |
6 |
Correct |
227 ms |
25248 KB |
Output is correct |
7 |
Correct |
58 ms |
25248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
25248 KB |
Output is correct |
2 |
Correct |
26 ms |
25248 KB |
Output is correct |
3 |
Correct |
13 ms |
25248 KB |
Output is correct |
4 |
Correct |
3 ms |
25248 KB |
Output is correct |
5 |
Correct |
10 ms |
25248 KB |
Output is correct |
6 |
Correct |
144 ms |
25248 KB |
Output is correct |
7 |
Correct |
11 ms |
25248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
25248 KB |
Output is correct |
2 |
Correct |
122 ms |
25248 KB |
Output is correct |
3 |
Correct |
13 ms |
25248 KB |
Output is correct |
4 |
Correct |
11 ms |
25248 KB |
Output is correct |
5 |
Correct |
93 ms |
25248 KB |
Output is correct |
6 |
Correct |
17 ms |
25248 KB |
Output is correct |
7 |
Correct |
172 ms |
25340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
435 ms |
25344 KB |
Output is correct |
2 |
Correct |
33 ms |
25344 KB |
Output is correct |
3 |
Correct |
12 ms |
25344 KB |
Output is correct |
4 |
Correct |
671 ms |
25352 KB |
Output is correct |
5 |
Correct |
102 ms |
25352 KB |
Output is correct |
6 |
Correct |
12 ms |
25352 KB |
Output is correct |
7 |
Correct |
22 ms |
25352 KB |
Output is correct |