// cre: Nguyen Ngoc Hung - Train VOI 2024
#include<bits/stdc++.h>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define gcd __gcd
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i+=c)
#define endl "\n"
#define int ll
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 2e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T> bool mini(T &a, const T &b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, const T &b){if(a<b){a=b;return true;}return false;}
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
int a[MAXN],n,m;
void sub1(){
int res = 0;
REP(state,0,MASK(n)-1){
int s = 0;
REP(i,0,n-1){
if(BIT(state,i)) s += a[i];
}
if(s<=m) ++res;
}
cout << res;
}
void sub2(){
int n1 = n/2,n2 = n-n1;
vi v1,v2;
REP(state,0,MASK(n1)-1){
int s = 0;
REP(i,0,n1-1) if(BIT(state,i)) s += a[i];
v1.push_back(s);
}
REP(state,0,MASK(n2)-1){
int s = 0;
REP(i,0,n2-1) if(BIT(state,i)) s += a[n1+i];
v2.push_back(s);
}
sort(ALL(v1)); sort(ALL(v2));
int res = 0;
for(const auto &u:v1){
int it = upper_bound(ALL(v2),m-u)-v2.begin();
res += it;
}
cout << res;
}
void solve(){
cin >> n >> m; REP(i,0,n-1) cin >> a[i];
sub2(); return ;
if(n<=20){
sub1(); return ;
}
sub2();
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
#define name1 "nnhzzz"
if(fopen(name1".inp","r")){
freopen(name1".inp","r",stdin);
freopen(name1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
Compilation message
bobek.cpp: In function 'int main()':
bobek.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bobek.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bobek.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen(name1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bobek.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | freopen(name1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
2140 KB |
Output is correct |
2 |
Correct |
77 ms |
5584 KB |
Output is correct |
3 |
Correct |
351 ms |
22568 KB |
Output is correct |
4 |
Correct |
76 ms |
5580 KB |
Output is correct |
5 |
Correct |
13 ms |
1752 KB |
Output is correct |
6 |
Correct |
8 ms |
1112 KB |
Output is correct |
7 |
Correct |
16 ms |
1756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
3032 KB |
Output is correct |
2 |
Correct |
27 ms |
2144 KB |
Output is correct |
3 |
Correct |
130 ms |
11876 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
7 ms |
992 KB |
Output is correct |
6 |
Correct |
17 ms |
1952 KB |
Output is correct |
7 |
Correct |
17 ms |
1756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
3676 KB |
Output is correct |
2 |
Correct |
113 ms |
8364 KB |
Output is correct |
3 |
Correct |
116 ms |
8524 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
73 ms |
7112 KB |
Output is correct |
6 |
Correct |
281 ms |
21904 KB |
Output is correct |
7 |
Correct |
103 ms |
6632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
230 ms |
14256 KB |
Output is correct |
2 |
Correct |
26 ms |
2144 KB |
Output is correct |
3 |
Correct |
9 ms |
1116 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
7 ms |
1116 KB |
Output is correct |
6 |
Correct |
218 ms |
14076 KB |
Output is correct |
7 |
Correct |
17 ms |
1884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
2144 KB |
Output is correct |
2 |
Correct |
79 ms |
5576 KB |
Output is correct |
3 |
Correct |
8 ms |
1116 KB |
Output is correct |
4 |
Correct |
9 ms |
1028 KB |
Output is correct |
5 |
Correct |
77 ms |
8264 KB |
Output is correct |
6 |
Correct |
24 ms |
2144 KB |
Output is correct |
7 |
Correct |
295 ms |
22572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
310 ms |
21496 KB |
Output is correct |
2 |
Correct |
26 ms |
2144 KB |
Output is correct |
3 |
Correct |
9 ms |
1116 KB |
Output is correct |
4 |
Correct |
352 ms |
21304 KB |
Output is correct |
5 |
Correct |
105 ms |
11904 KB |
Output is correct |
6 |
Correct |
16 ms |
1756 KB |
Output is correct |
7 |
Correct |
33 ms |
3032 KB |
Output is correct |