Submission #1121559

#TimeUsernameProblemLanguageResultExecution timeMemory
1121559vjudge1Ice Hockey World Championship (CEOI15_bobek)C++17
100 / 100
385 ms8644 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define endl "\n" using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T, typename key = less_equal<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; void solve() { ll n, m; cin >> n >> m; ll a[n]; for (ll &i : a) cin >> i; ll ans = 0; if (n <= 20) { for (ll msk = 0; msk < (1 << n); msk++) { ll sum = 0; for (ll i = 0; i < n; i++) if (msk >> i & 1) sum += a[i]; if (sum <= m) ans++; } } else { vector<ll> v; for (ll msk = 0; msk < (1 << (n - 20)); msk++) { ll sum = 0; for (ll i = 20; i < n; i++) if (msk >> (i - 20) & 1) sum += a[i]; v.push_back(sum); } sort(v.begin(), v.end()); for (ll msk = 0; msk < (1 << 20); msk++) { ll sum = 0; for (ll i = 0; i < 20; i++) if (msk >> i & 1) sum += a[i]; ans += upper_bound(v.begin(), v.end(), m - sum) - v.begin(); } } cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); // cin >> t; for (ll cs = 1; cs <= t; cs++) solve(); // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#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...