This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int N, mid;
long long M;
long long cost[40];
void smallM(){
vector<long long int> dp(M+1, 0);
dp[0] = 1;
for(int match = 0; match < N; ++match){
for(long long val = M; val > 0; --val){
if(cost[match] <= val) dp[val] += dp[val - cost[match]];
}
}
long long ans = 0;
for(int i = 0; i <= M; ++i) ans += dp[i];
cout << ans << endl;
}
int binarySearch(long long key, vector<long long>& V){
//maximo i tal que V[i] <= key
int lo = 0;
int hi = (int)V.size()-1;
int ans = -1;
while(lo <= hi){
int m = lo + (hi - lo)/2;
if(V[m] <= key){
ans = m;
lo = m+1;
}else hi = m-1;
}
return ans;
}
void print(vector<long long> & V){
for(int x: V) cout << x << " ";
cout << endl;
}
int main(){
cin >> N >> M;
for(int i = 0; i < N; ++i) cin >> cost[i];
mid = N/2;
vector<long long int>nums;
for(int mask = 0; mask < (1 << mid); ++mask){
long long sum = 0;
for(int i = 0; i < mid; ++i){
if(mask & (1 << i))sum += cost[i];
}
nums.push_back(sum);
}
sort(nums.begin(), nums.end());
//print(nums);
long long ans = 0;
for(int mask = 0; mask < (1 << (N - mid)); ++mask){
long long sum = 0;
for(int i = 0; i < (N - mid); ++i){
if(mask & (1 << i))sum += cost[i + mid];
}
long long pos = binarySearch(M - sum, nums);
//cout << sum << " " << pos << endl;
ans += pos + 1;
}
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |