#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ cin>>x; }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }
ll data[42];
typedef pair<ll,ll> pll;
ll tmp[(1<<20)+5];
vector<pll> work(int dl,int dr){
int n=dr-dl;
int am=(1<<n);
for(int i=0; i<am; ++i){
ll s=0;
for(int j=0; j<n; ++j){
if(1&(i>>j)){
s += data[dl+j];
}
}
tmp[i]=s;
}
sort(tmp, tmp+am);
vector<pll> ret;
for(int i=0; i<am;){
int j;
for(j=i; j<am && tmp[i]==tmp[j]; ++j);
ret.pb({tmp[i], j-i});
i=j;
}
return ret;
}
#define BIG
vector<pll> vl, vr;
int main(){
int n; ll m;
read(n, m);
for(int i=0; i<n; ++i){
ll t;
read(t);
data[i]=t;
}
int hn = n/2;
vl=work(0, hn); vr=work(hn, n);
int sl=sz(vl);
for(int i=1; i<sl; ++i)
vl[i].second += vl[i-1].second;
ll ans=0;
auto il=vl.begin(), ir=vr.end();
while(ir != vr.begin()){
--ir;
while(il != vl.end()){
auto it=il; ++it;
if(it == vl.end()) break;
if(it->first + ir->first <= m){
il=it;
} else break;
}
if(il != vl.end() &&
il->first + ir->first <= m)
ans += il->second*ir->second;
}
printf("%lld\n", ans);
return 0;
}
Compilation message
bobek.cpp: In function 'void read(int&)':
bobek.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(int& x){ scanf("%d",&x); }
~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
360 KB |
Output is correct |
2 |
Correct |
3 ms |
528 KB |
Output is correct |
3 |
Correct |
3 ms |
648 KB |
Output is correct |
4 |
Correct |
2 ms |
648 KB |
Output is correct |
5 |
Correct |
2 ms |
648 KB |
Output is correct |
6 |
Correct |
2 ms |
680 KB |
Output is correct |
7 |
Correct |
2 ms |
680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
688 KB |
Output is correct |
2 |
Correct |
2 ms |
692 KB |
Output is correct |
3 |
Correct |
3 ms |
700 KB |
Output is correct |
4 |
Correct |
3 ms |
760 KB |
Output is correct |
5 |
Correct |
2 ms |
764 KB |
Output is correct |
6 |
Correct |
3 ms |
768 KB |
Output is correct |
7 |
Correct |
2 ms |
772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
800 KB |
Output is correct |
2 |
Correct |
3 ms |
800 KB |
Output is correct |
3 |
Correct |
2 ms |
804 KB |
Output is correct |
4 |
Correct |
2 ms |
804 KB |
Output is correct |
5 |
Correct |
2 ms |
812 KB |
Output is correct |
6 |
Correct |
2 ms |
816 KB |
Output is correct |
7 |
Correct |
2 ms |
820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
2356 KB |
Output is correct |
2 |
Correct |
96 ms |
11680 KB |
Output is correct |
3 |
Correct |
466 ms |
28468 KB |
Output is correct |
4 |
Correct |
111 ms |
28468 KB |
Output is correct |
5 |
Correct |
49 ms |
28468 KB |
Output is correct |
6 |
Correct |
11 ms |
28468 KB |
Output is correct |
7 |
Correct |
26 ms |
28468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
28468 KB |
Output is correct |
2 |
Correct |
42 ms |
28468 KB |
Output is correct |
3 |
Correct |
168 ms |
28468 KB |
Output is correct |
4 |
Correct |
2 ms |
28468 KB |
Output is correct |
5 |
Correct |
8 ms |
28468 KB |
Output is correct |
6 |
Correct |
24 ms |
28468 KB |
Output is correct |
7 |
Correct |
24 ms |
28468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
28468 KB |
Output is correct |
2 |
Correct |
139 ms |
28468 KB |
Output is correct |
3 |
Correct |
142 ms |
28468 KB |
Output is correct |
4 |
Correct |
2 ms |
28468 KB |
Output is correct |
5 |
Correct |
90 ms |
28468 KB |
Output is correct |
6 |
Correct |
334 ms |
28468 KB |
Output is correct |
7 |
Correct |
151 ms |
28468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
316 ms |
33884 KB |
Output is correct |
2 |
Correct |
41 ms |
33884 KB |
Output is correct |
3 |
Correct |
17 ms |
33884 KB |
Output is correct |
4 |
Correct |
3 ms |
33884 KB |
Output is correct |
5 |
Correct |
10 ms |
33884 KB |
Output is correct |
6 |
Correct |
330 ms |
33900 KB |
Output is correct |
7 |
Correct |
27 ms |
33900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
33900 KB |
Output is correct |
2 |
Correct |
105 ms |
33900 KB |
Output is correct |
3 |
Correct |
14 ms |
33900 KB |
Output is correct |
4 |
Correct |
16 ms |
33900 KB |
Output is correct |
5 |
Correct |
106 ms |
33900 KB |
Output is correct |
6 |
Correct |
39 ms |
33900 KB |
Output is correct |
7 |
Correct |
436 ms |
50308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
466 ms |
50308 KB |
Output is correct |
2 |
Correct |
41 ms |
50308 KB |
Output is correct |
3 |
Correct |
15 ms |
50308 KB |
Output is correct |
4 |
Correct |
470 ms |
50308 KB |
Output is correct |
5 |
Correct |
126 ms |
50308 KB |
Output is correct |
6 |
Correct |
25 ms |
50308 KB |
Output is correct |
7 |
Correct |
51 ms |
50308 KB |
Output is correct |