Submission #1125038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125038		cpismayilmmdv985	Ice Hockey World Championship (CEOI15_bobek)	C++20	100 / 100	286 ms	20900 KiB

bobek

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10