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 << (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 ptr = msa.size() - 1;
FOR(i, 0, msb.size() - 1){
while(ptr != -1 && msa[ptr] + msb[i] > c) ptr--;
r += ptr + 1;
}
cout << r << endl;
}
Compilation message (stderr)
bobek.cpp: In function 'int main()':
bobek.cpp:5:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define FOR(i, a, b) for(ll i = a; i <= b; i++)
......
57 | FOR(i, 0, msb.size() - 1){
| ~~~~~~~~~~~~~~~~~~~~
bobek.cpp:57:5: note: in expansion of macro 'FOR'
57 | FOR(i, 0, msb.size() - 1){
| ^~~
# | 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... |