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>
#define ll long long
using namespace std;
ll n, m, arr[50], res1[1100010], res2[1100010], ans;
vector<ll> dp1, dp2;
void find(int idx, ll mon, int cur, int lim, ll res[]) {
if(cur > lim) {
res[idx] = mon;
return;
}
if(mon + arr[cur] <= m) find(idx+pow(2, lim-cur), mon+arr[cur], cur+1, lim, res);
find(idx, mon, cur+1, lim, res);
if(cur == lim) res[idx] = mon;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1; i<=n; i++) {
cin >> arr[i];
}
for(int i=0; i<1100010; i++) {
res1[i] = -1;
res2[i] = -1;
}
find(0, 0, 1, n/2, res1);
find(0, 0, (n/2)+1, n, res2);
for(int i=0; i<1100010; i++) {
if(res1[i] != -1) dp1.push_back(res1[i]);
if(res2[i] != -1) dp2.push_back(res2[i]);
}
sort(dp2.begin(), dp2.end());
for(int i=0; i<dp1.size(); i++) {
ans += lower_bound(dp2.begin(), dp2.end(), m-dp1[i]+1) - dp2.begin();
}
cout << ans;
return 0;
}
Compilation message (stderr)
bobek.cpp: In function 'int main()':
bobek.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0; i<dp1.size(); i++) {
| ~^~~~~~~~~~~
# | 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... |