Submission #441567

#TimeUsernameProblemLanguageResultExecution timeMemory
441567dynam1cIce Hockey World Championship (CEOI15_bobek)C++17
100 / 100
531 ms8524 KiB
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" #define all(c) (c).begin(),(c).end() // when you ponder, divide and conquer signed main() { // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); std::ios::sync_with_stdio(false); cin.tie(0); int n; ll m; cin >> n >> m; vector<ll> arr(n); for (int i = 0; i < n; i++) cin >> arr[i]; vector<ll> ee(1<<(n/2)); for (int b = 0; b < 1<<(n/2); b++) { ll x = 0; for (int l = 0; l < 20; l++) if (b>>l & 1) x += arr[l]; ee[b] = x; } sort(all(ee)); ll res = 0; for (int b = 0; b < 1<<(n-n/2); b++) { ll x = 0; for (int l = 0; l < 20; l++) if (b>>l & 1) x += arr[n/2+l]; res += upper_bound(all(ee), m-x) - ee.begin(); } cout << res << endl; } /* --- PSolving --- * Simplifying (getting rid of variables, conditions, code logic, etc.) * Reframing * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.) * Inducing * Divide and conquer * Working backwards * Visual intuition * !! Reductions don't have to be specializations, they can be generalizations */
#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...