제출 #1125038

#제출 시각아이디문제언어결과실행 시간메모리
1125038cpismayilmmdv985Ice Hockey World Championship (CEOI15_bobek)C++20
100 / 100
286 ms20900 KiB
#include <bits/stdc++.h> using namespace std; template<typename T1, typename T2>ostream& operator<<(ostream &os, const pair<T1, T2> &p) {return os << '{' << p.first << ", " << p.second << '}';} template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } template <typename K, typename V> ostream& operator<<(ostream& os, const map<K, V>& m) {os << "{";for (auto it = m.begin(); it != m.end(); ++it) {if (it != m.begin()) os << ", "; os << it->first << " : " << it->second;}return os << "}";} void debug() { cerr << endl; } template<typename Head, typename... Tail> void debug(Head H, Tail... T) { cerr << H; debug(T...); } #ifdef VOID_DEBUG #define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", debug(__VA_ARGS__) #else #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define deb(...) #endif const int mxN = 5e3 + 5; const int mod = 1e9 + 7; const int dx4[] = {1, -1, 0, 0}, dy4[] = {0, 0, -1, 1}; const int dx8[] = {1, -1, 0, 0, 1, -1, 1, -1}, dy8[] = {0, 0, -1, 1, 1, -1, -1, 1}; void run_case() { int n; int64_t m; cin >> n >> m; vector<int64_t> v; for (int64_t i = 0, x; i < n; i++) { cin >> x; if (x <= m) v.push_back(x); } sort(v.begin(), v.end()); n = v.size(); map<int64_t, int> mp1, mp2; vector<int64_t> v1, v2, sum1, sum2; for (int i = 0; i < (n >> 1); i++) v1.push_back(v[i]); for (int i = (n >> 1); i < n; i++) v2.push_back(v[i]); for (int mask = 1; mask < (1 << v1.size()); mask++) { int64_t sum = 0; for (int i = 0; i < v1.size(); i++) { if (mask & (1 << i)) { sum += v1[i]; } } if (sum <= m) sum1.push_back(sum); } for (int mask = 1; mask < (1 << v2.size()); mask++) { int64_t sum = 0; for (int i = 0; i < v2.size(); i++) { if (mask & (1 << i)) { sum += v2[i]; } } if (sum <= m) sum2.push_back(sum); } sort(sum1.begin(), sum1.end()); sort(sum2.begin(), sum2.end()); int64_t ans = 1 + sum1.size() + sum2.size(); for (int i = 0; i < sum2.size(); i++) { auto it = upper_bound(sum1.begin(), sum1.end(), m - sum2[i]) - sum1.begin(); ans += it; } cout << ans; // debug(mp1), debug(mp2); // map<int64_t, int> mp; // for (auto &i : mp1) mp[i.first] += i.second; // for (auto &i : mp2) mp[i.first] += i.second; // for (auto &i : mp1) { // for (auto &j : mp2) { // if (i.first + j.first <= m) mp[i.first + j.first] += i.second * j.second; // else break; // } // } // for (auto &i : mp) ans += i.second; // cout << ans; return; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int test_case = 1; // cin >> test_case; for (int num_case = 1; num_case <= test_case; num_case++) { run_case(); } 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...