Submission #447483

#TimeUsernameProblemLanguageResultExecution timeMemory
447483ak2006Ice Hockey World Championship (CEOI15_bobek)C++14
100 / 100
527 ms8652 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } int n = 40; ll m; vl a(n); int main() { setIO(); cin>>n>>m; for (int i = 0;i<n;i++)cin>>a[i]; int pivot = n/2; //generate all subsets of the first pivot integers (0 to pivot - 1) //generate all subsets of the remaining n - pivot integers (pivot to n - 1) //sort the first subset and for each number in the second subset, find //the last position in the first subset such that the number there + the current element in the //subset is <= m //if sum + X > m //then X > m - sum vl firstSubset; for (int mask = 0;mask<(1<<pivot);mask++){ ll sum = 0; for (int i = 0;i<pivot;i++) if (mask & (1<<i))sum += a[i]; firstSubset.pb(sum); } sort(firstSubset.begin(),firstSubset.end()); ll cnt = 0; for (int mask = 0;mask<(1<<(n - pivot));mask++){ ll sum = 0; for (int i = pivot;i<n;i++) if (mask & (1<<(i - pivot)))sum += a[i]; cnt += upper_bound(firstSubset.begin(),firstSubset.end(),m - sum) - firstSubset.begin(); } cout<<cnt; return 0; }
#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...