Submission #1121645

#TimeUsernameProblemLanguageResultExecution timeMemory
1121645vjudge1Ice Hockey World Championship (CEOI15_bobek)C++17
100 / 100
437 ms20908 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long vector<ll> getSubsetSum(const vector<ll>& subset) { vector<ll> subsetSums; int n = subset.size(); for (int i = 0; i < (1 << n); ++i) { ll sum = 0; for (int j = 0; j < n; ++j) { if (i & (1 << j)) { sum += subset[j]; } } subsetSums.push_back(sum); } return subsetSums; } ll countWays(int N, ll M, const vector<ll>& costs) { vector<ll> leftHalf(costs.begin(), costs.begin() + N / 2); vector<ll> rightHalf(costs.begin() + N / 2, costs.end()); vector<ll> leftSums = getSubsetSum(leftHalf); vector<ll> rightSums = getSubsetSum(rightHalf); sort(rightSums.begin(), rightSums.end()); ll count = 0; for (ll leftSum : leftSums) { if (leftSum <= M) { count += upper_bound(rightSums.begin(), rightSums.end(), M - leftSum) - rightSums.begin(); } } return count; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); int N; ll M; cin >> N >> M; vector<ll> costs(N); for (ll &i : costs) cin >> i; ll result = countWays(N, M, costs); cout << result << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...