#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
long long n,m,a[1000005],p,l,r,mid,ans,sum;
vector <long long> v,v1;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
v.pb(0);
for(int i=1;i<=(n/2);i++){
p=v.size();
for(int j=0;j<p;j++){
if(v[j]+a[i]<=m){
v.pb(v[j]+a[i]);
}
}
}
if(a[(n/2)+1]<=m){
v1.pb(a[(n/2)+1]);
}
for(int i=(n/2)+2;i<=n;i++){
p=v1.size();
for(int j=0;j<p;j++){
if(v1[j]+a[i]<=m){
v1.pb(v1[j]+a[i]);
}
}
}
for(int i=0;i<v1.size();i++){
l=0;
r=v.size()-1;
while(l<=r){
mid=(l+r)/2;
if(v[mid]<=(m-v1[i])){
l=mid+1;
ans=mid;
}else{
r=mid-1;
}
}
sum+=(ans+1);
}
sum+=(v1.size());
sum+=(v.size());
cout<<sum<<endl;
}
/*
########################### ########################## ################################
##################################### #################### ############################################## ############################### ############################### ##################################
##################################### #################### ################################################## ################################# ################################# ####################################
##################################### #################### ###################################################### ################################### ################################### ######################################
##################################### #################### ######################################################### ############ ######### ######## ############ ########################################
##################################### #################### ############### ############ ######### ######## ############ ############ ############
##################################### #################### ############### ############ ######### ######## ############ ############ ############
################# #################### ############### ############ ######### ######## ############ ############ ############
################# #################### ############### ############ #################### ############ ############ ############
################# ############### ############ ################# ############ ############ ############
################# #################### ############### ############ ############## ############ ############ ############
################# #################### ############### ############ ############ ############ ############ ############
################# #################### ############### ############ ########## ############ ############ ############
##################################### #################### ############### ############ ###### ############ ############ ############
##################################### #################### ############### ############ #### ############ ############################################################
##################################### #################### ############### ###################### ############ ############ ##############################################################
##################################### #################### ############### ###################### ############ ############ ################################################################
##################################### #################### ############### ############ ############ ############ ############ ############
##################################### #################### ############### ############ ############ ############ ############ ############
##################### #################### ############### ############ ############ ############ ############ ############
##################### #################### ############### ############ ############ ############ ############ ############
##################### #################### ############### ############ ############ ############ ############ ############
##################### #################### ############### ############ ############ ############ ############ ############
##################### #################### ############### ############ ############ ############ ############ ############
##################### #################### ############### ############ ############ ############ ############ ############
##################################### #################### ######################################################## ############ ############ ############ ############
##################################### #################### ####################################################### ############ ############ ############ ############
##################################### #################### ##################################################### ############ ############ ############ ############
##################################### #################### ################################################# ############ ############ ############ ############
*/
Compilation message
bobek.cpp: In function 'int main()':
bobek.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<v1.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
10532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
16708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
