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;
#define ll long long
#define MAXN 45
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
ll n, c, m[MAXN], r = 1;
int main(){
cin >> n >> c;
FOR(i, 1, n) cin >> m[i];
sort(m + 1, m + 1 + n);
if(n == 1) {
cout << (1 + (m[1] <= c)) << endl;
return 0;
}
pair<ll, ll> a = {1, (1 + n) / 2}, b = {(1 + n) / 2 + 1, n};
// solve first half
ll mska = pow(2, a.second - a.first + 1);
vector<ll> msa;
FOR(msk, 1, mska - 1){
ll s = 0;
FOR(i, a.first, a.second){
if(msk & (1 << (i - a.first))){
s += m[i];
}
}
if(s > c) continue;
r++;
msa.push_back(s);
}
sort(begin(msa), end(msa));
// solve second half
ll mskb = pow(2, b.second - b.first + 1);
vector<ll> msb;
FOR(msk, 1, mskb - 1){
ll s = 0;
FOR(i, b.first, b.second){
if(msk & (1 << (i - b.first))){
s += m[i];
}
}
if(s > c) continue;
r++;
msb.push_back(s);
}
sort(begin(msb), end(msb));
// combine both halves
ll na = (ll)msa.size(), nb = (ll)msb.size();
ll ptr = na - 1;
FOR(i, 0, nb - 1){
while(ptr >= 0 && msa[ptr] + msb[i] > c) {
ptr--;
}
r += ptr + 1;
}
cout << r << endl;
}
/*
8 1232
143 321241 53 1532 123 3253 32513 1232
*/
# | 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... |